Module 4 TREES

28/11/2025 School of Computer Engineering, MIT, Manipal 1

General View

28/11/2025 School of Computer Engineering, MIT, Manipal 2

Data Structures View

28/11/2025 School of Computer Engineering, MIT, Manipal 3

TREES
• A tree is a finite set of one or more nodes such that:
• There is a specially designated node called the root.
• The remaining nodes (if any) are partitioned into n >= 0 disjoint sets ,
• each of these sets is itself a tree.
• These trees are called the subtrees of the root.

• Applications:
• –Organization charts
• –File systems
• –Programming environments

28/11/2025 School of Computer Engineering, MIT, Manipal 4

Linear DS Vs Non-Linear DS

Feature Linear DS Non-Linear DS

Hierarchical (tree) or Network
Arrangement Sequential (one after another)
(graph)
Relationship One-to-one One-to-many / many-to-many
Traversal Simple (for loop, while loop) Complex (DFS, BFS)
Usually continuous (array) or
Memory Random nodes linked via pointers
linked sequentially
Examples Array, Stack, Queue, Linked List Tree, Graph

28/11/2025 School of Computer Engineering, MIT, Manipal 5

 Tree Terminology
•Root: Node without a parent. The starting point of the tree.
•Siblings: Nodes that share the same parent.
•Internal node: Node with at least one child.
•External node (leaf): Node without children.
•Ancestors of a node: All nodes along the path from the root to the parent of the node (parent, grandparent,
etc.).
•Descendants of a node: All nodes in the subtree rooted at the node, excluding the node itself (children,
grandchildren, etc.).
•Depth of a node: The number of nodes on the path from the root to the node.
•Example: If the root is included, depth(root) = 1.
•Height of a node: The number of nodes in the longest path from that node down to a leaf.
•Example: If the node is a leaf, its height = 1.
•Height of the tree: The height of the root node; i.e., the number of nodes on the longest path from root to a
leaf.
•Degree of a node: The number of children of the node.
•Degree of a tree: The maximum degree among all nodes in the tree.
•Subtree: A tree consisting of a node and all its descendants.

28/11/2025 School of Computer Engineering, MIT, Manipal 6

EXAMPLE
• A is the root node
• B is the parent of D and E
• C is the sibling of B
• D and E are the children of B
• D, E, F, G, I are external nodes, or leaves
• A, B, C, H are internal nodes
• The height of the node A is 4
• The depth of the node A is 1
• The degree of node B is 2
• The degree of the tree is 3
• The ancestors of node I is A, C, H
• The descendants of node C is F, G, H, I
What will be the height of the node B & C ?

28/11/2025 School of Computer Engineering, MIT, Manipal 7

Height and Depth Difference
• Height and depth of a tree is
equal...
• but height and depth of a node is
not equal because... depth 2 depth 2
Height 2 Height 3

• the height is calculated by

traversing from the given node to
the deepest possible leaf. depth 3
Height 1
depth 3
Height 1
depth 3
Height 2

• depth is calculated from traversal

from root to the given node.....
depth 4
Height 1

28/11/2025 School of Computer Engineering, MIT, Manipal 8

Representation of Tree

List Representation

Left Child-Right Sibling Representation

28/11/2025 School of Computer Engineering, MIT, Manipal 9

 1. List Representation

A (A)

B C D ( A ( B, C, D ) )

E F G H I J ( A ( B ( E, F ), C ( G ), D ( H, I, J ) ) )

K L M ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )

K
E
B
L
F
A C G

H M
D I
J
28/11/2025 School of Computer Engineering, MIT, Manipal 10
 2. FirstChild-NextSibling Representation (Left Child Right Sibling)

Element A
N
FirstChild NextSibling

B C D
A N

B C D
E F G H I J
E F G H I J N N N N N N N

K L M K L M
N N N N N

Note: The representation is not unique since the children in a

tree can be of any order.

28/11/2025 School of Computer Engineering, MIT, Manipal 11

Binary Tree

binary trees are an important type of tree structure that occurs

very often.

The chief characteristic of a binary tree is the stipulation that

the degree of any given node must not exceed two.

28/11/2025 School of Computer Engineering, MIT, Manipal 12

Binary Trees
A binary tree is a tree in which no node can have more than two children.

Rotate the FirstChild-NextSibling tree clockwise by 45.

A A
N
45
B

N
E
B C D
N K C
F

N
E F G H I J L G

N
D

N
NN NN N NN

N
N

N
H

N
K L M
N NN NN M I

N
N
Left J

N
Element

N
N
Left Right
Right

28/11/2025 School of Computer Engineering, MIT, Manipal 13

7/16
Tree Representation

28/11/2025 School of Computer Engineering, MIT, Manipal 14

 The BinaryTree ADT extends the Tree ADT,
i.e., it inherits all the methods of the Tree
Binary Tree ADT ADT
Additional methods:

–position leftChild(p)

–position rightChild(p)

–position sibling(p)

Update methods may be defined by data

structures implementing the BinaryTree
ADT

28/11/2025 School of Computer Engineering, MIT, Manipal 15

Binary Tree Properties

28/11/2025 School of Computer Engineering, MIT, Manipal 16

Minimum Number Of Nodes
• Minimum number of nodes in a binary tree whose height is h.
• At least one node at each of first h levels.

minimum number of nodes is h

28/11/2025 School of Computer Engineering, MIT, Manipal 17

 Maximum Number of Nodes in BT

 The maximum number of nodes on level i of a binary tree is 2i-1,

i>=1.
 The maximum number of nodes in a binary tree
of depth k is 2k-1, k>=1.

Prove by induction.
k
 2 i 1
2 k
1
i 1

28/11/2025 School of Computer Engineering, MIT, Manipal 18 18

 Full Binary Tree
•Definition: A binary tree in which every node has either 0 or 2 children (no
node has only one child).
•Key Point: Each node is "full" — either it’s a leaf or it has two children.
•Shape Constraint: No restriction on how "balanced" the tree is; it can be
skewed in height as long as each node has 0 or 2 children.

Complete Binary Tree

•Definition: A binary tree in which all levels are completely filled except possibly
the last level, and in the last level, all nodes are as far left as possible.
•Key Point: Structure is almost like a "filled array representation" of a heap.
•Shape Constraint: Must be filled level by level, left to right.

28/11/2025 School of Computer Engineering, MIT, Manipal 19

 Samples of Trees
Complete Binary Tree

A A 1 A

B B 2 B C

C Skewed Binary Tree

3 D E F G
D

4 H I
E 5

28/11/2025 School of Computer Engineering, MIT, Manipal 20 20

 Full BT VS Complete BT
 A full binary tree of depth k is a binary tree of
depth k having 2k – 1 nodes, k>=1.
 A binary tree with n nodes and depth k is
complete iff all of its nodes are filled except possibly the last level,
where in the last level the nodes are filled from left to right .

A A

B C B C

D E F G D E F G

H I J K L M N O
H I
Complete binary tree Full binary tree of depth 4

28/11/2025 School of Computer Engineering, MIT, Manipal 21

Key Difference

Feature Full Binary Tree Complete Binary Tree

Node Children Each node has 0 or 2 children Nodes can have 0, 1, or 2 children

Leaf Node Placement Can be at different levels Must be as far left as possible

Last Level Requirement No specific requirement Filled left to right

Structural Symmetry Focused on node completeness Focused on level-wise filling

28/11/2025 School of Computer Engineering, MIT, Manipal 22

Binary Tree Representation
• Array representation.
• Linked representation.

28/11/2025 School of Computer Engineering, MIT, Manipal 23

 [1]
Sequential Representation [2]
A
B
[3] C
(1) waste space
A [1] A (2) insertion/deletion [4] D
[2] B problem [5] E
[3] -- [6] F
B [7]
[4] C A G
[5] -- [8] H
C [6] -- [9] I
B C
[7] --
D [8] D
D E F G
[9] --
E . .
[16] E H I

28/11/2025 School of Computer Engineering, MIT, Manipal 24

28/11/2025 School of Computer Engineering, MIT, Manipal 25
 Advantages and disadvantages of Array representation

Advantages:
1. This representation is very easy to understand.
2. This is the best representation for full and complete binary tree
representation.
3. Programming is very easy.
4. It is very easy to move from a child to its parents and vice versa.

Disadvantages:
5. Lot of memory area wasted.
6. Insertion and deletion of nodes needs lot of data movement.
7. This is not suited for trees other than full and complete tree.

28/11/2025 School of Computer Engineering, MIT, Manipal 26

 Linked Representation
struct node {
int data;
node *left_child, *right_child;
};

data

left_child data right_child

left_child right_child

28/11/2025 School of Computer Engineering, MIT, Manipal 27 27

Linked Representation Example

28/11/2025 School of Computer Engineering, MIT, Manipal 28

 Advantages and disadvantages of linked representation

Advantages
1. A particular node can be placed at any location in the memory.
2. Insertions and deletions can be made directly without data movements.
3. It is best for any type of trees.
4. It is flexible because the system take care of allocating and freeing of
nodes.
Disadvantage
5. It is difficult to understand.
6. Additional memory is needed for storing pointers
7. Accessing a particular node is not easy.

28/11/2025 School of Computer Engineering, MIT, Manipal 29

Implementation
// Node structure // Function to allocate a new node
typedef struct Node { Nodeptr getnode() {
int data; Nodeptr temp = (Nodeptr)malloc(sizeof(struct Node));
struct Node *lchild; if (!temp) {
struct Node *rchild; printf("Memory allocation failed!\n");
} *Nodeptr; exit(1);
}
temp->lchild = temp->rchild = NULL;
return temp;
}

28/11/2025 School of Computer Engineering, MIT, Manipal 30

Implementation
// Recursive function to create a binary tree
Nodeptr CreateBinaryTree(int item) {
int x;
if (item != -1) { // -1 indicates no node
Nodeptr temp = getnode();
temp->data = item;
printf("Enter the lchild of %d (-1 for no child): ", item);
scanf("%d", &x);
temp->lchild = CreateBinaryTree(x);
printf("Enter the rchild of %d (-1 for no child): ", item);
scanf("%d", &x);
temp->rchild = CreateBinaryTree(x);
return temp;
}
return NULL;
}

28/11/2025 School of Computer Engineering, MIT, Manipal 31

 Binary Tree Traversals
• Binary tree operations often require traversing the tree.
• In a traversal, each node is visited exactly once.
• During the visit, any operation on the node can be performed, such as:
• Displaying the node
• Cloning the node
• Evaluating operators in an expression tree
Types of Binary Tree Traversals
• Preorder Traversal (Root → Left → Right)
• Inorder Traversal (Left → Root → Right)
• Postorder Traversal (Left → Right → Root)
• Level-order Traversal (Breadth-first)

28/11/2025 School of Computer Engineering, MIT, Manipal 32

Pre order Traversal-Recursive
• void preorderTraversal(struct Node* node)
•{
• if (node == NULL) {
• return; }
• printf("%d ", node->data); // Print the data of the current node
• preorderTraversal(node->left); // Recursively traverse the left subtree
• preorderTraversal(node->right); // Recursively traverse the right subtree
•}

28/11/2025 School of Computer Engineering, MIT, Manipal 33

Preorder Example (Visit = print)
a

b c

a b c

28/11/2025 School of Computer Engineering, MIT, Manipal 34

Preorder Example (Visit = print)
a

b c
f
d e
g h i j

a b d g h e i c f j

28/11/2025 School of Computer Engineering, MIT, Manipal 35

In order Traversal- Recursive
// Function to perform inorder traversal on a binary tree
void inorderTraversal(struct Node* node) {
if (node == NULL) {
return;
}
inorderTraversal(node->left); // Recursively traverse the left subtree
printf("%d ", node->data); // Print the data of the current node
inorderTraversal(node->right); // Recursively traverse the right subtree
}

28/11/2025 School of Computer Engineering, MIT, Manipal 36

Inorder Example (Visit = print)
a

b c

b a c

28/11/2025 School of Computer Engineering, MIT, Manipal 37

Inorder Example (Visit = print)
a

b c
f
d e
g h i j

g d h b e i a f j c

28/11/2025 School of Computer Engineering, MIT, Manipal 38

 Inorder By Projection (Squishing)
a

b c
f
d e
g h i j

g d h b e i a f j c

28/11/2025 School of Computer Engineering, MIT, Manipal 39

Post order Traversal- Recursive
• // Function to perform postorder traversal on a binary tree
• void postorderTraversal(struct Node* node) {
• if (node == NULL) {
• return;
• }
• postorderTraversal(node->left); // Recursively traverse the left subtree
• postorderTraversal(node->right); // Recursively traverse the right subtree
• printf("%d ", node->data); // Print the data of the current node
•}

28/11/2025 School of Computer Engineering, MIT, Manipal 40

Postorder Example (Visit = print)
a

b c

b c a

28/11/2025 School of Computer Engineering, MIT, Manipal 41

Postorder Example (Visit = print)
a

b c
f
d e
g h i j

g h d i e b j f c a

28/11/2025 School of Computer Engineering, MIT, Manipal 42

 • // Function for pre-order traversal
(Iterative)
• void preOrderTraversal(struct Node* root) {
• if (root == NULL)
• return;
• struct Node* stack[100];
Pre order Traversal- • int top = -1;
• stack[++top] = root;
Iterative
• while (top != -1) {
• struct Node* current = stack[top--];
• printf("%d ", current->data);
• if (current->right != NULL)
• stack[++top] = current->right;
• if (current->left != NULL)
• stack[++top] = current->left; }}
28/11/2025 School of Computer Engineering, MIT, Manipal 43
 • // Function for in-order traversal (Iterative)
• void inOrderTraversal(Node* root) {
• Node* stack[MAX_SIZE];
• int top = -1;
• Node* current = root;
In order Traversal- • while (current != NULL || top > -1) // pop
Iterative • {
• while (current != NULL) // travel leftmost of current
subtree
• {stack[++top] = current;
• current = current->left; }
• current = stack[top--];
• printf("%d ", current->data);
• current = current->right;
• } }

28/11/2025 School of Computer Engineering, MIT, Manipal 44

 • // Function for post-order traversal (Iterative)

• void postorder(struct Node* root) {

• if (root == NULL)
• return;
Post order Traversal- • struct Node* current = root;
• struct Node* prev = NULL;
Iterative
• struct Node* stack[100];
• int top = -1;
• do { while (current != NULL) {
• stack[++top] = current;
• current = current->left;
• }

28/11/2025 School of Computer Engineering, MIT, Manipal 45

 • while (current == NULL && top != -1) {
• current = stack[top];
• // If the right child is either not present or has been visited

Post order Traversal- •

{
if (current->right == NULL || current->right == prev)

Iterative • printf("%d ", current->data); top--;

• prev = current;
• current = NULL; }
• // Else traverse the right child
• else {
• current = current->right;
• }
• } } while (top != -1);}

28/11/2025 School of Computer Engineering, MIT, Manipal 46

 Traversal Applications
a

b c
f
d e
g h i j

• Make a clone.
• Determine height.
•Determine number of nodes.

28/11/2025 School of Computer Engineering, MIT, Manipal 47

Level Order Traversal
• Unlike preorder, inorder, and postorder (which are DFS traversals), Level Order
Traversal is a BFS traversal that visits nodes level by level from left to right.
It uses a queue for implementation.

• It is a breadth-first search (BFS) technique where we visit all nodes at each level
from left to right before moving to the next level

• Start at the root

• Visit the nodes at each level, from left to right

28/11/2025 School of Computer Engineering, MIT, Manipal 48

Algorithm for Level Order Traversal
The standard way to implement level order traversal is by using
a queue.
1. Start from the root node and initialize a queue.
2. Push the root node into the queue.
3. While the queue is not empty:
• Dequeue a node from the front of the queue and print its value.
• If the dequeued node has a left child, enqueue the left child.
• If the dequeued node has a right child, enqueue the right child.
4. Continue this process until the queue becomes empty, meaning
all nodes have been processed.

28/11/2025 School of Computer Engineering, MIT, Manipal 49

Level Order Traversal
A

B C

D E F G

H I

Nodes will be visited in the order ABCDEFGHI

28/11/2025 School of Computer Engineering, MIT, Manipal 50

 Level Order Traversal
• Start at the root
• Visit the nodes at each level, from left to right

B C

D E F G

queue
H I

28/11/2025 School of Computer Engineering, MIT, Manipal 51

 Level Order Traversal
• Start at the root
• Visit the nodes at each level, from left to right

B C

D E F G

H I
A

28/11/2025 School of Computer Engineering, MIT, Manipal 52

 Level Order Traversal
• Start at the root
• Visit the nodes at each level, from left to right

B C

D E F G

H I

28/11/2025
A School of Computer Engineering, MIT, Manipal 53
 Level Order Traversal
• Start at the root
• Visit the nodes at each level, from left to right

B C

D E F G

H I
BC

28/11/2025
A School of Computer Engineering, MIT, Manipal 54
 Level Order Traversal
• Start at the root
• Visit the nodes at each level, from left to right

B C

D E F G

H I
C

28/11/2025
A B School of Computer Engineering, MIT, Manipal 55
 Level Order Traversal
• Start at the root
• Visit the nodes at each level, from left to right

B C

D E F G

H I
CDE

28/11/2025
A B School of Computer Engineering, MIT, Manipal 56
 Level Order Traversal
• Start at the root
• Visit the nodes at each level, from left to right

B C

D E F G

H I
DEFG

28/11/2025
A B C School of Computer Engineering, MIT, Manipal 57
 Level Order Traversal
• Start at the root
• Visit the nodes at each level, from left to right

B C

D E F G

H I
EFGH

28/11/2025
A B C D School of Computer Engineering, MIT, Manipal 58
 Level Order Traversal
• Start at the root
• Visit the nodes at each level, from left to right

B C

D E F G

H I
FGH

28/11/2025
A B C D E School of Computer Engineering, MIT, Manipal 59
 Level Order Traversal
• Start at the root
• Visit the nodes at each level, from left to right

B C

D E F G

H I
GHI

28/11/2025
A B C D EF
School of Computer Engineering, MIT, Manipal 60
 Level Order Traversal
• Start at the root
• Visit the nodes at each level, from left to right

B C

D E F G

H I
HI

28/11/2025
A B C D E School
F Gof Computer Engineering, MIT, Manipal 61
 Level Order Traversal
• Start at the root
• Visit the nodes at each level, from left to right

B C

D E F G

H I
I

28/11/2025
A B C D E School
F Gof Computer
H Engineering, MIT, Manipal 62
 Level Order Traversal
• Start at the root
• Visit the nodes at each level, from left to right

B C

D E F G

H I

28/11/2025
A B C D E School
F Gof Computer
H I Engineering, MIT, Manipal 63
 Level order Traversal
• void levelOrderTraversal(struct Node* root) {
• if (root == NULL) return;
• // Create a queue for level order traversal

• struct Queue* queue = createQueue(100);

• enqueue(queue, root);
• while (!isEmpty(queue)) {
• struct Node* current = dequeue(queue);
• printf("%d ", current->data);
• // Enqueue left child

• if (current->left != NULL)
• enqueue(queue, current->left);
• // Enqueue right child

• if (current->right != NULL)
• enqueue(queue, current->right);
• }}
28/11/2025 School of Computer Engineering, MIT, Manipal 64
 Additional Binary Tree
Operations

28/11/2025 School of Computer Engineering, MIT, Manipal 65

 Searching
• Searching an item in the tree can be done while traversing the
tree in inorder, preorder or postorder traversals.

• While visiting each node during traversal, instead of printing

the node info, it is checked with the item to be searched.

• If item is found, search is successful.

28/11/2025 School of Computer Engineering, MIT, Manipal 66

 Searching a binary tree
int Search(Nodeptr root,int ele) //uses preorder traversal
{
static int t=0;
if(root)
{
if(root->data==ele){
t++;
return t;
}
if (t==0) Search(root->lchild,ele);
if (t==0) Search(root->rchild,ele);
}
}

28/11/2025 School of Computer Engineering, MIT, Manipal 67

 Creating a copy of a binary tree
Getting the exact copy of the given tree.
/*recursive function to copy a tree*/
Nodeptr copy (Nodeptr root){
Nodeptr temp;
if(root == NULL)
return NULL;
temp=getnode();
tempdata=rootdata;
templchild=copy(rootlchild);
temprchild=copy(rootrchild);
return temp;
}

28/11/2025 School of Computer Engineering, MIT, Manipal 68

 Counting the number of nodes in a tree
Traverse the tree in any of the 3 techniques and every time a node
is visited, count is incremented.
void count_nodes( Nodeptr root)
{
static int count = 0;
if(root!=NULL)
{
count_nodes(rootllink);
count++;
count_nodes(rootrlink);
} return count;}

28/11/2025 School of Computer Engineering, MIT, Manipal 69

 Counting the number of leaf nodes in a binary tree
Every time a node is visited, check whether the right and left link of
that node is NULL. If yes, count is incremented.
/*counting number of leaf nodes using inorder technique*/
int count_leafnodes( Nodeptr root){
static int count = 0;
if(root!=NULL){
if(root->lchild==NULL && root->rchild==NULL)
count++;
count_leafnodes(root->lchild);
count_leafnodes(root->rchild);
} return count; }
28/11/2025 School of Computer Engineering, MIT, Manipal 70
 Equality of 2 binary trees

Returns FALSE if the binary trees root1 and root2 are not equal
otherwise returns TRUE
int Equal( Nodeptr root1, Nodeptr root2)
{
return ((!root1 && !root2) || (root1 && root2 && (root1data ==
root2data) && Equal( root1->lchild,root2->lchild) && Equal
( root1->rchild,root2->rchild));
}

28/11/2025 School of Computer Engineering, MIT, Manipal 71

 Expression Tree

An expression tree is a binary tree used to represent

expressions

28/11/2025 School of Computer Engineering, MIT, Manipal 72

 Using Binary Trees: Expression Trees
• Programs that manipulate or evaluate arithmetic expressions can use binary
trees to hold the expressions

• An expression tree represents an arithmetic expression such as

(5 – 3) * 4 + 9 / 2

• Root node and interior nodes contain operations (operator)

• Leaf nodes contain operands (variable or a constant)

28/11/2025 School of Computer Engineering, MIT, Manipal 73

 Example: An Expression Tree
+

* /

- 4 9 2

5 3

(5 – 3) * 4 + 9 / 2

28/11/2025 School of Computer Engineering, MIT, Manipal 74

Why use Expression Trees?

• Evaluation: You can easily evaluate the

expression by traversing the tree.

• Transformation: It helps transform infix,

postfix, or prefix expressions.

28/11/2025 School of Computer Engineering, MIT, Manipal 75

 Expression Tree Traversals
• Inorder Traversal: Yields the infix expression.
• Preorder Traversal: Yields the prefix expression.
• Postorder Traversal: Yields the postfix expression.
inorder traversal
+ A/ B*C*D+ E
infix expression
* E preorder traversal
+ **/ABCDE
prefix expression
* D postorder traversal
AB/ C*D*E+
/ C postfix expression
level order traversal
+ *E*D/ CAB
A B
28/11/2025 School of Computer Engineering, MIT, Manipal 76 76
Evaluating Expression Trees

• We can use an expression tree to evaluate an expression

• We start the evaluation at the bottom left
• What kind of traversal is this?

28/11/2025 School of Computer Engineering, MIT, Manipal 77

 Evaluating an Expression Tree
* This tree represents
the expression

+ - (9 / 2 + 7) * (8 – 5)

/ 7 8 5
Evaluation is based on postorder traversal:
9 2 If root node is a leaf, return the associated value.
Recursively evaluate expression in left subtree.
Recursively evaluate expression in right subtree.
Perform operation in root node on these two values,
and return result.

28/11/2025 School of Computer Engineering, MIT, Manipal 78

 Evaluating an Expression Tree

+ -

/ 7 8 5

9 2

28/11/2025 School of Computer Engineering, MIT, Manipal 79

 Evaluating an Expression Tree

+ -

4.5 / 7 8 5

9 2

28/11/2025 School of Computer Engineering, MIT, Manipal 80

 Evaluating an Expression Tree

11.5 + -

4.5 / 7 8 5

9 2

28/11/2025 School of Computer Engineering, MIT, Manipal 81

 Evaluating an Expression Tree

11.5 + 3 -

4.5 / 7 8 5

9 2

28/11/2025 School of Computer Engineering, MIT, Manipal 82

 Evaluating an Expression Tree

34.5
*

11.5 + 3 -

4.5 / 7 8 5

9 2

28/11/2025 School of Computer Engineering, MIT, Manipal 83

 Building an Expression Tree
• From Postfix Expression:
1.Initialize an empty stack.
2.Traverse the postfix expression from left to right.
3.For each symbol:
1. If it’s an operand, create a tree node and push it onto the stack.
2. If it’s an operator, pop two nodes from the stack, make them children of
a new operator node, and push the new node back onto the stack.
4.The final node in the stack is the root of the expression tree.

28/11/2025 School of Computer Engineering, MIT, Manipal 84

 Build an expression tree from the postfix
expression 5 3 - 4 * 9 +

Symbol Processing Step(s)

5 t = newNode (5,null, null); push(stack, t);

Expression Tree Stack (top at right)

Symbol Processing Step(s)

t = newNode (3,null, null); push(stack, t);
3
Expression Tree Stack (top at right)

5 3
28/11/2025 School of Computer Engineering, MIT, Manipal 85
 Symbol Processing Step(s)

- op2 = pop
op1 = pop
t = newNode (-,op1, op2);
push(stack, t);

Expression Tree Stack

5 3

28/11/2025 School of Computer Engineering, MIT, Manipal 86

 Symbol Processing Step(s)

4 t = newNode (4,null, null);

push(stack, t);

Expression Tree Stack (top at right)

- 4

5 3

28/11/2025 School of Computer Engineering, MIT, Manipal 87

 Symbol Processing Step(s)

* op2 = pop
op1 = pop
t = newNode (*,op1, op2);
push(stack, t);
Expression Tree Stack (top at right)

- 4

5 3

28/11/2025 School of Computer Engineering, MIT, Manipal 88

 Symbol Processing Step(s)

9 t = newNode (9,null, null);

push(stack, t);
Expression Tree Stack (top at right)

* 9

- 4

5 3

28/11/2025 School of Computer Engineering, MIT, Manipal 89

 Symbol Processing Step(s)
op2 = pop
+
op1 = pop
t = newNode (+,op1, op2); push(stack, t);

Expression Tree Stack (top at right)

+
End of the expression has
* 9 been reached, and the full
expression tree is the only
- 4 tree left on the stack

5 3

28/11/2025 School of Computer Engineering, MIT, Manipal 90

  Expression Trees

 Constructing an Expression Tree

(from postfix expression)

〖 Example 〗 ( a + b ) * ( c * ( d + e ) ) = a b + c d e + * *

+
a b *c d * +
e

T2 T2 a + b c T1 d * + e T1 T1

a bT2 T2 c d + e T1

d e
28/11/2025 School of Computer Engineering, MIT, Manipal 91
8/16
 Threaded Binary Tree
Threads
• In a linked representation of a binary tree, there are more NULL
links than actual pointers.

• In a binary tree with n nodes containing 2n links, there are n+1

NULL links.

• Perlis and Thornton devised a way to make use of NULL links.

• Here the NULL links are replaced by pointers, called threads, to

other nodes in the tree.

28/11/2025 School of Computer Engineering, MIT, Manipal 92

 Threaded Binary Tree

Threading Rules
• A NULL RightChild field at node p is replaced by a pointer to
the node that would be visited after p when traversing the tree in
inorder. That is, it is replaced by the inorder successor of p.
• A NULL LeftChild link at node p is replaced by a pointer to the
node that immediately precedes node p in inorder (i.e., it is
replaced by the inorder predecessor of p).

28/11/2025 School of Computer Engineering, MIT, Manipal 93

 A Binary Tree

B C

D E F G

H I

Inorder sequence: H, D, I, B, E, A, F, C,
G
28/11/2025 School of Computer Engineering, MIT, Manipal 94
 Threaded Tree Corresponding to Given Binary Tree

B C

D E F G

H I

Inorder sequence: H, D, I, B, E, A, F, C,
G
28/11/2025 School of Computer Engineering, MIT, Manipal 95
 Threads
• To distinguish between normal pointers and threads,
two boolean fields, LeftThread and RightThread, are
added to the record in memory representation.
• t->leftThread= TRUE
=> t->lchild is a thread
• t->leftThread= FALSE
Þ t->lchild is a pointer to the left child.
• t->rightThread= TRUE
=> t->rchild is a thread
• t->rightThread= FALSE
=> t->rchild is a pointer to the right child.

28/11/2025 School of Computer Engineering, MIT, Manipal 96

 Threaded Binary Tree Node Structure Declaration

typedef struct threadedTree *threadedPointer;

struct threadedTree{
short int leftThread;
threadedPointer lchild;
char data;
threadedPointer rchild;
short int rightThread;
};

28/11/2025 School of Computer Engineering, MIT, Manipal 97

 Threads (Cont.)

• To avoid dangling threads, a head node is used in

representing a binary tree.
• The original tree becomes the left subtree of the head
node.
• Empty Binary Tree

leftThread lchild data rchild rightThread

TRUE FALSE

28/11/2025 School of Computer Engineering, MIT, Manipal 98

 Memory Representation of Threaded Tree

F - F

F A F

F B f F C F

F D F T E T T F T T G T

T H T T I T

28/11/2025 School of Computer Engineering, MIT, Manipal 99

 Finding the inorder successor without stack
By using the threads, we can perform an inorder
traversal without making use of a stack.

threadedPointer insucc(threadedPointer node)

{ //Return the inorder successor of node
threadedPointer temp = node-> rchild;
if (node->rightThread==FALSE)
while (temp->leftThread==FALSE)
temp = temp -> lchild;
return temp;
}
28/11/2025 School of Computer Engineering, MIT, Manipal 100
 Inorder Traversal of a threaded Binary Tree
void tinorder(threadedPointer treehead)
{
threadedPointer temp = treehead;
while(1){
temp = insucc(temp);
if (temp == treehead) break;
printf(“%c”, temp->data);
}
}

28/11/2025 School of Computer Engineering, MIT, Manipal 101

Threaded Tree Traversal
• We start at the leftmost node in the tree, print it, and follow its right
thread
• If we follow a thread to the right, we output the node and continue to
its right
• If we follow a link to the right, we go to the leftmost node, print it, and
continue

28/11/2025 School of Computer Engineering, MIT, Manipal 102

Threaded Tree Traversal
Output
6 1

3 8
1 5 7 11
9 13
Start at leftmost node, print it

28/11/2025 School of Computer Engineering, MIT, Manipal 103

Threaded Tree Traversal
Output
6 1
3

3 8
1 5 7 11
9 13
Follow thread to right, print node

28/11/2025 School of Computer Engineering, MIT, Manipal 104

Threaded Tree Traversal
Output
6 1
3

3 8 5

1 5 7 11
9 13
Follow link to right, go to
leftmost node and print

28/11/2025 School of Computer Engineering, MIT, Manipal 105

Threaded Tree Traversal
Output
6 1
3

3 8 5
6

1 5 7 11
9 13
Follow thread to right, print node

28/11/2025 School of Computer Engineering, MIT, Manipal 106

Threaded Tree Traversal
Output
6 1
3

3 8 5
6
7
1 5 7 11
9 13
Follow link to right, go to
leftmost node and print

28/11/2025 School of Computer Engineering, MIT, Manipal 107

Threaded Tree Traversal
Output
6 1
3

3 8 5
6
7
1 5 7 11 8

9 13
Follow thread to right, print node

28/11/2025 School of Computer Engineering, MIT, Manipal 108

Threaded Tree Traversal
Output
6 1
3

3 8 5
6
7
1 5 7 11 8
9

9 13
Follow link to right, go to
leftmost node and print

28/11/2025 School of Computer Engineering, MIT, Manipal 109

Threaded Tree Traversal
Output
6 1
3

3 8 5
6
7
1 5 7 11 8
9
11
9 13
Follow thread to right, print node

28/11/2025 School of Computer Engineering, MIT, Manipal 110

Threaded Tree Traversal
Output
6 1
3

3 8 5
6
7
1 5 7 11 8
9
11
9 13 13

Follow link to right, go to

leftmost node and print

28/11/2025 School of Computer Engineering, MIT, Manipal 111

 Inserting A Node to AThreaded Binary Tree
• Inserting a node r as the right child of a node s.
• If s has an empty right subtree, then the insertion is
simple (as shown in diagram next slide)
• If the right subtree of s is not empty, then, this right
subtree is made the right subtree of r after insertion. When
this is done, r becomes the inorder predecessor of a node
that has a leftThread==TRUE field, and consequently
there is an thread which has to be updated to point to r.
The node containing this thread was previously the
inorder successor of s. Figure illustrates the insertion for
this case.

28/11/2025 School of Computer Engineering, MIT, Manipal 112

 Insertion of r As A Right Child of s in A Threaded Binary Tree

s s

r r

before after
28/11/2025 School of Computer Engineering, MIT, Manipal 113
 Insertion of r As A Right Child of s in A Threaded Binary Tree
(Cont.)

s s

r r

before after
28/11/2025 School of Computer Engineering, MIT, Manipal 114
Advantages
• Efficient Traversal: Threaded binary trees allow for linear and fast traversal of nodes in the
tree without the need for a stack. This eliminates the memory and time overhead associated
with stack-based traversal methods.

• Reduced Memory Consumption: Since threaded binary trees do not require a stack for
traversal, they consume less memory compared to other traversal methods that rely on
recursion or iterative approaches with stacks.

• Quick Successor and Predecessor Determination: In threaded binary trees, it is easy to

determine the successor and predecessor of any node by following the thread and links. This
allows for efficient retrieval and manipulation of neighboring nodes, similar to a circular linked
list.

28/11/2025 School of Computer Engineering, MIT, Manipal 115

 Binary Search Tree (BST)
• Definition: A binary search tree is a binary tree. It may be empty. If it
is not empty then it satisfies the following properties:
• Every node has exactly one key and no two nodes have the same
key (i.e., the keys in the tree are distinct)
• The keys (if any) in the left subtree are smaller than the key in the
root.
• The keys (if any) in the right subtree are larger than the key in the
root.
• The left and right subtrees are also binary search trees.
• Inorder traversal of BST results in ascending order of elements

28/11/2025 School of Computer Engineering, MIT, Manipal 116

 Binary Tree vs BST

30 60
20

5 40 70
15 25

65 80
14 10 22 2

Not binary Binary

search tree search trees
28/11/2025 School of Computer Engineering, MIT, Manipal 117
 Difference between BT and BST
▪ A binary tree is simply a tree in which each node can have
at most two children.
▪ A binary search tree is a binary tree in which the nodes are
assigned values, with the following restrictions :
1. No duplicate values.
2. The left subtree of a node can only have values less than
the node and recursively defined
3. The right subtree of a node can only have values greater
than the node and recursively defined
4. The left subtree of a node is a binary search tree.
5. The right subtree of a node is a binary search tree.
28/11/2025 School of Computer Engineering, MIT, Manipal 118
 Recursive function to create a BST
Nodeptr CreateBST(Nodeptr root, int item){
if (root==NULL){
root = getnode();
root->data= item;
root->lchild=root->rchild = NULL;
return root;
}
else
if (item<root->data)
root->lchild = CreateBST(root->lchild, item);
else
if (item>root->data)
root->rchild = CreateBST(root->rchild, item);
else
printf("Duplicates are not allowed\n");
return root;
28/11/2025
} School of Computer Engineering, MIT, Manipal 119
 Searching in A Binary Search Tree

• If the root is NULL, then this is an empty tree. No search is

needed.
• If the root is not NULL, compare the x with the key of root.
• If x equals to the key of the root, then it’s done.
• If x is less than the key of the root, then no elements in the
right subtree can have key value x. We only need to search
the left tree.
• If x larger than the key of the root, only the right subtree is
to be searched.

28/11/2025 School of Computer Engineering, MIT, Manipal 120

 Searching in A Binary Search Tree
if the tree is empty
return NULL

else if the key value in the node(root) equals the

target return the node value

else if the key value in the node is greater than the

target return the result of searching the left
subtree

else if the key value in the node is smaller than the

target return the result of searching the right
28/11/2025 School of Computer Engineering, MIT, Manipal 121
subtree
 Searching a BST
typedef struct node *Nodeptr;
struct node{
int data;
Nodeptr rchild;
Nodeptr lchild;
};
Nodeptr search(Nodeptr root,int key)
{
/* return a pointer to the node that contains key. If there is no such node, return NULL */

if (root==NULL) return NULL;

if (key == root->data) return root;
if (key < root->data)
return search(root->lchild, key);
return search(root->rchild,key);
28/11/2025} School of Computer Engineering, MIT, Manipal 122
 Iterative Searching Algorithm
Nodeptr itersearch(Nodeptr root, int key)
{
while (root) {
if (key == root->data) return root;
if (key < root->data)
root = root->lchild;
else root = root->rchild;
}
return NULL;
}

28/11/2025 School of Computer Engineering, MIT, Manipal 123

 Other operations:
1. Finding the maximum element in BST: maximum
element will always be the last right child in a BST.
Move to the rightmost node in a BST and you will
end up in the maximum element.
2. Finding the minimum element: Move to the leftmost
child and you will reach the least element in BST.
3. Finding the height of a tree: height is nothing but
maximum level in the tree plus one. It can be easily
found using recursion.

28/11/2025 School of Computer Engineering, MIT, Manipal 124

 Insertion To A Binary Search Tree
• Before insertion is performed, a search must be done to make
sure that the value to be inserted is not already in the tree.
• If the search fails, then we know the value is not in the tree.
So, it can be inserted into the tree.
• If item is lesser than the root item, move to left or else move
to the right of root node.
• This process is repeated until the correct position is found.

28/11/2025 School of Computer Engineering, MIT, Manipal 125

 10 10

8 15 8 15

5 9 12 17 5 9 12 17

13

To insert item 13 to above BST

• Compare with the root item. 13> 10, hence move to right and
reach 15.
• Now 13<15, So go to left and reach 12.
• 13>12, hence move right.
• Now the correct position is found and hence insert the new node
to the right of 12.

28/11/2025 School of Computer Engineering, MIT, Manipal 126

 10
10

7 15
7 15

5 9 12 17
5 9 12 17

To insert 8 into the above tree

• Compare with root item. 8<10, hence move left and
reach 7.
• Now 8>7. So move right and reach 9.
• 8<9. Move left and the correct position is obtained.
• Insert 8 to the left of 9.
28/11/2025 School of Computer Engineering, MIT, Manipal 127
 Insertion Into A Binary Search Tree
typedef struct node *Nodeptr; /*traverse until correct position is found*/
struct node{ parent=NULL;
int data; cur=*root;
while(cur){
Nodeptr rchild; parent=cur;
Nodeptr lchild; if (item==cur->data ){
printf("Duplicates Not allowed");
}; free(temp);
void Insert(Nodeptr *root, int item){ return;
}
Nodeptr temp= getnode(); else if (item<cur->data)
cur=cur->lchild;
temp->data = item; else
temp->lchild = NULL; cur=cur->rchild;
}
temp->rchild = NULL; if (item<parent->data)
if (*root==NULL) { parent->lchild = temp;
else
*root = temp; return; parent->rchild = temp;
return;
} }
Nodeptr parent, cur;
28/11/2025 School of Computer Engineering, MIT, Manipal 128
 Deletion From A Binary Search Tree
• Delete a leaf node
• A leaf node which is a right child of its parent
• A leaf node which is a left child of its parent
• Delete a non-leaf node
• A node that has one child
• A node that has two children
• Replaced by the largest element in its left subtree, or
• Replaced by the smallest element in its right subtree

28/11/2025 School of Computer Engineering, MIT, Manipal 129

 Deleting From A Binary Search Tree
leaf non-leaf
node node

30 30

5 40 2
5 40

2 35 80 2 80

28/11/2025 School of Computer Engineering, MIT, Manipal 130

 Deletion from a Binary Search Tree
non-leaf
40 45
node

20 60 20 60

10 30 50 70 10 30 50 70

45 55 55

52 52
Before deleting 40 After deleting 40

28/11/2025 School of Computer Engineering, MIT, Manipal 131

Function for BST Delete ( Replaced by the smallest element in its right subtree)

void Delete(Nodeptr *root, int item){

Nodeptr parent, cur;
Nodeptr q, succ;

if (*root== NULL){
printf("Empty Tree\n"); return;
}
//traverse the tree until the item is found or entire tree is traversed
parent = NULL;
cur = *root;
while(cur && (cur->data!= item)){
parent = cur;
if (item<cur->data)
cur = cur->lchild;
else
cur = cur->rchild;
}
if (cur==NULL) {
printf("Item Not Found\n");
return;
28/11/2025 } School of Computer Engineering, MIT, Manipal 132
Function for BST Delete ( Replaced by the smallest element in its right
subtree)
//item found and check for case 1
if (cur->lchild == NULL) //node to be deleted has empty left subtree
q= cur->rchild; //get the address of right subtree
else if (cur->rchild == NULL) //node to be deleted has empty right subtree
q = cur->lchild; //get the address of left subtree
else //interior node
{
//find inorder successor->smallest element in the right subtree
parent = cur;
succ = cur->rchild; //get address of rightchild of node to be deleted*/

while (succ->lchild){ //move to the leftmost node of succ

parent = succ;
succ= succ->lchild;
}
cur->data = succ->data;//exchange the data of current and succ;
cur = succ;
q = cur->rchild;
}
28/11/2025 School of Computer Engineering, MIT, Manipal 133
Function for BST Delete ( Replaced by the smallest element in its right subtree)

if (parent == NULL){
free(cur);
*root = q;
return;
}
if (cur== parent->lchild)
parent->lchild = q;
else
parent->rchild = q;
free(cur);
return;
}

28/11/2025 School of Computer Engineering, MIT, Manipal 134

 Applications for BST
 Binary Search Tree: Used in many search applications where data is constantly
entering/leaving, such as the map and set objects in many languages' libraries.
Binary Space Partition: Used in almost every 3D video game to determine
 what objects need to be rendered.
Binary Tries: Used in almost every high-bandwidth router for storing router-tables.
 Heaps: Used in implementing efficient priority-queues. Also used in heap-sort.
Huffman Coding Tree:- used in compression algorithms, such as those used
by the .jpeg and .mp3 file-formats.

GGM Trees - Used in cryptographic applications to generate a tree of pseudo-
random numbers.
 Syntax Tree: Constructed by compilers and (implicitly) calculators to parse
expressions.

28/11/2025 School of Computer Engineering, MIT, Manipal 135

AVL TREE

28/11/2025 School of Computer Engineering, MIT, Manipal 136

What is a Degenerate BST?
• A degenerate binarysearch tree is one
where most or all of the nodes
contain only one sub node.
• It is unbalanced and, in the worst
case, performance degrades to that
of a linked list.
• If your add node function does not
handle rebalancing, then you can
easily construct a degenerate tree by
feeding it data that is already sorted.

28/11/2025 School of Computer Engineering, MIT, Manipal 137

 Does the order of inserting
elements into a tree matter?
 Yes, certain orders might produce very
unbalanced trees or degenerated
trees!

 Advanced tree structures, such as red-black

trees, AVL trees, guarantee balanced trees.

28/11/2025 School of Computer Engineering, MIT, Manipal 138

Does the order of inserting elements into
a tree matter?

28/11/2025 School of Computer Engineering, MIT, Manipal 139

 Unbalanced trees are not desirable because
search time increases!

Advanced tree structures, such as red-black

trees, AVL trees, guarantee balanced trees.

28/11/2025 School of Computer Engineering, MIT, Manipal 140

Better Search Trees
• Prevent the degeneration of the BST :
• A BST can be set up to maintain balance during
updating operations (insertions and removals)
• Types of ST which maintain the optimal
performance in other words balanced trees:
• splay trees
• AVL trees
• 2-4 Trees
• Red-Black trees
• B-trees

28/11/2025 School of Computer Engineering, MIT, Manipal 141

 An AVL (Adelson-Velskii and Landis) tree is a
binary search tree with a balance condition.

A tree is said to be balanced if for each node, the

number of nodes in the left subtree and the number
AVL TREE of nodes in the right subtree differ by at most one.

A tree is said to be height-balanced or AVL if for

each node, the height of the left subtree and the
height of the right subtree differ by at most one.

Height of AVL tree is 1.44log(N+2) -0.328 »

logN and the searching complexity » O(log N)

28/11/2025 School of Computer Engineering, MIT, Manipal 142

 AVL Tree Definition

• Binary tree.

• If T is a nonempty binary tree with TL and TR as its left and right sub trees,
then T is an AVL tree iff

• TL and TR are AVL trees, and

•|hL – hR| <= 1 where hL and hR are the heights of TL and TR, respectively

28/11/2025 School of Computer Engineering, MIT, Manipal 143

 Balance Factor

• AVL trees are normally represented using the linked representation

• To facilitate insertion and deletion, a Balance Factor (BF) is associated with each
node
• Balance Factor = Height(Left-sub tree) - Height(Right-sub tree)) (i.e.) hL-hR
• Balance factor of each node in an AVL tree must be –1, 0, or 1
-1: height of the right sub tree is one greater than the left sub-tree.
0: height of the left and right sub-trees is equal.
+1: height of the left sub-tree is one greater than the right sub-tree.

28/11/2025 School of Computer Engineering, MIT, Manipal 144

 • Example
-1
10

7 1
40
1

0 3 0 8 1 30 -

415
0 -1
0 0 0
1 5 20 35 60

25

28/11/2025 School of Computer Engineering, MIT, Manipal 145

 Properties of AVL Tree

• The height of an AVL tree with n nodes is O(log n)

• For every value of n, n  0, there exists an AVL tree

• An n-node AVL search tree can be searched in O(height) =

O(log n) time
• A new node can be inserted into an n-node AVL search tree so
that the result is an n+1 node AVL tree and insertion can
be done in O(log n) time

28/11/2025 School of Computer Engineering, MIT, Manipal 146

 • A node can be deleted from an n-node AVL search tree, n>0,
so that the result is an n-1 node AVL tree and deletion can
be done in O(log n) time
• After insertion and deletion of any node in an AVL tree if the
balance factor of any node becomes other than -1, 0, +1
then it is said that AVL property is violated. Then we have to
restore the destroyed balance condition.
• The balancing should be such that the entire tree should satisfy
AVL property.

28/11/2025 School of Computer Engineering, MIT, Manipal 147

 Insertion into an AVL Tree

• To insert an element into an AVL search tree, the result may not be an AVL tree.
(i.e.) the tree may become unbalanced
• If the tree becomes unbalanced, we must adjust the tree to restore balance - this
adjustment is called rotation
• There are four different cases when rebalancing is required after insertion of
new node.
• left sub tree of left child (LL )
• right sub tree of left child (RL )
• left sub tree of right child (LR )
• right sub tree of right child (RR )
28/11/2025 School of Computer Engineering, MIT, Manipal 148
 Definition of Rotation
• Any modification done on an AVL tree in order to rebalance it is called a rotation of an AVL
tree.

• Types of rotations are

1. Single Rotation

• LL rotation(Left-Left)

• RR rotation(Right Right)

28/11/2025 School of Computer Engineering, MIT, Manipal 149

2. Double Rotation

• LR rotation(Left-Right) - The transformation to correct LR

imbalance can be achieved by an RR rotation followed by an LL rotation.

• RL rotation(Right-Left) - The transformation to correct RL imbalance can be

achieved by an LL rotation followed by an RR rotation.

28/11/2025 School of Computer Engineering, MIT, Manipal 150

 Insertion Algorithm

• Create new node and insert a new node as leaf node as in ordinary
binary search tree.
• Now track the path from insertion point towards root.
• Checks each node of heights of left (n) and right (n) differ by at most 1.
If yes, move towards parent(n)
Otherwise restructure by doing either a single or double rotation.

28/11/2025 School of Computer Engineering, MIT, Manipal 151

 Single Rotation
•(a)LL rotation [ Insert Left , Rotate
Right] General

LL rotation

28/11/2025 School of Computer Engineering, MIT, Manipal 152

 Example:
BF=1 2 0

Insert Node 1 1
LL rotation 0
0
0

BF=0
Balanced Tree
Unbalanced Tree

When node 1 is inserted to the left of 2, the tree becomes

unbalanced hence rotate right (LL rotation) to make the balanced
tree

28/11/2025 School of Computer Engineering, MIT, Manipal 153

 RR rotation [ Insert Right, Rotate
Left]

RR rotation

28/11/2025 School of Computer Engineering, MIT, Manipal 154

 Example:

BF=-1
-2 0
Insert Node 3 RR rotation
-1

BF=0 0 0
0

Unbalanced Tree Balanced Tree

• When node 3 is inserted to the right of 2, the tree becomes

unbalanced hence rotate left(RR rotation) to make the balanced tree

28/11/2025 School of Computer Engineering, MIT, Manipal 155

 Double Rotation
• LR rotation [ RR rotation followed by an LL
rotation ]

RR rotation LL rotation

28/11/2025 School of Computer Engineering, MIT, Manipal 156

 Example

BF=1 0
2 2
Insert Node 2 RR rotation
LL rotation
-1 1
0
0 0
0
BF=0
Unbalanced Tree Unbalanced Tree
Balanced Tree

When node 2 is inserted to the right of 1, the tree becomes

unbalanced hence rotate left (RR
unbalanced rotation), still it is
balanced treehence rotate right (LL rotation)
28/11/2025 School of Computer Engineering, MIT, Manipal 157
 RL rotation [ LL rotation followed by an RR rotation ]
• General

LL rotation RR rotation

28/11/2025 School of Computer Engineering, MIT, Manipal 158

 Example
0
BF=-1 -2 -2
Insert node 2 RR rotation
LL rotation -1
1
0 0
BF=0 0
0
Unbalanced Tree Unbalanced Tree Balanced Tree

• When node 2 is inserted to the left of 3, the tree becomes

unbalanced hence rotate right (LL rotation), still it is unbalanced

hence rotate left (RR rotation) to make a balanced tree.
28/11/2025 School of Computer Engineering, MIT, Manipal 159
Example of Insertions in an AVL Tree

1
20 Insert 5, 40
0 1
10 30
0 0
25 35

28/11/2025 School of Computer Engineering, MIT, Manipal 160

Example of Insertions in an AVL Tree

0
1
20 20
1 0 0 1
10 30 10 30
0 0 0 -1
0 0
5 25 35 5 25 35
0
40
Now Insert 45

28/11/2025 School of Computer Engineering, MIT, Manipal 161

Single rotation

2
1
20 20
1 -2 1 -1
10 30 10 30
0 0 -2
0 0
5 25 35 5 25 40 0
0 0
35 45
Imbalance 1 40

0 45
Now Insert 34

28/11/2025 School of Computer Engineering, MIT, Manipal 162

Double rotation

-2
-1
20 20
1 -2 1 0
10 30 10 35
0 0 1
0 0
5 Imbalance 25 40 5 30 40 -1
0
1 0 25 34 45
35 45 0
Insertion of 34 0
34

28/11/2025 School of Computer Engineering, MIT, Manipal 163

 Example 2: AVL Tree
Insert 3,2,1,4,5,6,7, 16,15,14

3 2
3
3

2 1
Fig 1 2 3
Fig 4
Fig 2
2 1 2

Fig 3
1 3
1 3
Fig 5 Fig 6 4
4 5

28/11/2025 School of Computer Engineering, MIT, Manipal 164

 2
2

1 4
1 4
3 5
3 5
Fig 8
Fig 7 6
4
4
2 5
2 5
1 3 6
1 3 6
4
Fig 10 7
Fig 9
2 6

1 3 7

5 Fig 11
28/11/2025 School of Computer Engineering, MIT, Manipal 165
 4 4

2 6 2 6

1 3 7 1 3 7

5 16 5 16
Fig 12
Fig 13
15
4

2 6

1 3 15
5
16
Fig 14 7

28/11/2025 School of Computer Engineering, MIT, Manipal 166

 4 4

2 2 7
6

15 1 3 15
1 3 5 6
16
7 5 14 16
Fig 15
14 Fig 16

Deletions can be done with similar rotations

28/11/2025 School of Computer Engineering, MIT, Manipal 167

Case Condition (Balance Factor) Rotation Example Description
Extra nodes on left-left
1. Left-Left (LL) BF(node) > 1 and BF(left child) ≥ 0 Right Rotation
side
Left–Right
2. Left-Right (LR) BF(node) > 1 and BF(left child) < 0 Left subtree’s right-heavy
Rotation
3. Right-Right Extra nodes on right-
BF(node) < –1 and BF(right child) ≤ 0 Left Rotation
(RR) right side
Right–Left
4. Right-Left (RL) BF(node) < –1 and BF(right child) > 0 Right subtree’s left-heavy
Rotation

28/11/2025 School of Computer Engineering, MIT, Manipal 168

 Implementation
#define MAX(a,b) ((a) > (b) ? (a) : (b))

// Node Declaration for AVL trees

typedef struct AvlNode {
int element;
struct AvlNode *left;
struct AvlNode *right;
int height;
} AvlNode;

28/11/2025 School of Computer Engineering, MIT, Manipal 169

 Implementation
• // Function to get height
• int height(AvlNode *t) {
• return t == NULL ? -1 : t->height;
• }
• // Single rotation with left child
• void rotateWithLeftChild(AvlNode **k2) {
• AvlNode *k1 = (*k2)->left;
• (*k2)->left = k1->right;
• k1->right = *k2;
• (*k2)->height = MAX(height((*k2)->left), height((*k2)->right)) + 1;
• k1->height = MAX(height(k1->left), (*k2)->height) + 1;
• *k2 = k1;
• }

28/11/2025 School of Computer Engineering, MIT, Manipal 170

Implementation
• // Single rotation with right child
• void rotateWithRightChild(AvlNode **k1) {
• AvlNode *k2 = (*k1)->right;
• (*k1)->right = k2->left;
• k2->left = *k1;
• (*k1)->height = MAX(height((*k1)->left), height((*k1)->right)) + 1;
• k2->height = MAX(height(k2->right), (*k1)->height) + 1;
• *k1 = k2;
• }

• // Double rotation: left-right // Double rotation: right-left

• void doubleWithLeftChild(AvlNode **k3) { void doubleWithRightChild(AvlNode **k3) {
• rotateWithRightChild(&((*k3)->left)); rotateWithLeftChild(&((*k3)->right));
• rotateWithLeftChild(k3); rotateWithRightChild(k3);
• } }

171
28/11/2025 School of Computer Engineering, MIT, Manipal
 Implementation
// Insert element into AVL tree
else if (x > (*t)->element) {
void insert(int x, AvlNode **t) {
insert(x, &((*t)->right));
if (*t == NULL) {
if (height((*t)->right) - height((*t)->left) == 2) {
*t = (AvlNode*)malloc(sizeof(AvlNode));
if (x > (*t)->right->element)
(*t)->element = x;
rotateWithRightChild(t);
(*t)->left = (*t)->right = NULL;
else
(*t)->height = 0;
doubleWithRightChild(t);
}
}
else if (x < (*t)->element) {
}
insert(x, &((*t)->left));
// Duplicate: do nothing
if (height((*t)->left) - height((*t)->right) == 2) {
if (x < (*t)->left->element)
(*t)->height = MAX(height((*t)->left), height((*t)->right)) + 1;
rotateWithLeftChild(t);
}
else
doubleWithLeftChild(t);
}
}

172
28/11/2025 School of Computer Engineering, MIT, Manipal
 Implementation
// Test the AVL tree
int main() {
• // In-order traversal AvlNode *root = NULL;
• void inorder(AvlNode *t) {
• if (t != NULL) { int arr[] = {30, 20, 40, 10, 25, 35, 50, 5};
int n = sizeof(arr)/sizeof(arr[0]);
• inorder(t->left);
• printf("%d ", t->element); for (int i = 0; i < n; i++)
• inorder(t->right); insert(arr[i], &root);
• }
printf("Inorder traversal of AVL tree:\n");
• } inorder(root);
printf("\n");

return 0;
}

28/11/2025 School of Computer Engineering, MIT, Manipal 173

 Deletion in AVL Trees

• The deletion algorithm is more complex than insertion algorithm.

• Search the node which is to be deleted

• If the node to be deleted is a leaf node then simply make it NULL to

remove.
• If the node to be deleted is not a leaf node then the node must be swapped
with its inorder successor. After swap we can remove this node.

28/11/2025 School of Computer Engineering, MIT, Manipal 1

7
4
 • Example:
• Case 1: Leaf Node

Delete 11

28/11/2025 School of Computer Engineering, MIT, Manipal 1

7
5
 • Case 2: One Child

Delete 12

28/11/2025 School of Computer Engineering, MIT, Manipal 1

7
6
 • Case 3: Two Child

Delete 14

28/11/2025 School of Computer Engineering, MIT, Manipal 1

7
7
 0
1 0

1 0 0 -1

0 0 0 0

28/11/2025 School of Computer Engineering, MIT, Manipal 1

7
8
 RED-BLACK TREES
• A red-black tree is a balanced binary search tree with the following
properties.
• Every node is colored red or black.

• The root is black.

• Every leaf is a NIL node, and is colored black.

• If a node is red, then both its children are black.

• Every simple path from a node to a descendant leaf contains the same
number of black nodes=black-height(x).

28/11/2025 School of Computer Engineering, MIT, Manipal 1

7
9
 Example:
26

17 41

NIL NIL
30 47

NIL 38 NIL 50

NIL NIL NIL NIL

28/11/2025 School of Computer Engineering, MIT, Manipal 1

8
0
 • Black-Height of a node:

h=4
26 bh =
2
h=1 h=3
bh = 1 17 41 bh =
2
NIL h=2 h=2
30 bh =
47 bh =
h=1 1
NIL 1 bh = 1
h=1
NIL 38 NIL 50 bh =
1
NIL NIL
NIL NIL

28/11/2025 School of Computer Engineering, MIT, Manipal 1

8
1
 • Height of a node : the number of edges in the longest path to a
leaf.
• Black-height of a node x: bh(x) is the number of black nodes
(including NIL) on the path from x to a leaf, not counting x
• A red-black tree with n internal nodes has height at most 2lg(n + 1).

Insertion in red-black tree

1) If empty tree create black root node
2) Insert new leaf node as red
a) If its parent is black then done
b) If parent is red
i) If black sibling rotate, recolor and done.
ii) If red sibling then recolor and check again.

28/11/2025 School of Computer Engineering, MIT, Manipal 1

8
2
 Example

The tree insert routine has just been called to insert node
"4" into the tree.
This is no longer a red-black tree - there are two successive
red nodes on the path
11 - 2 - 7 - 5 - 4
Mark the new node, x, and it's uncle, y.
y is red, so we have case 1 ...
28/11/2025 School of Computer Engineering, MIT, Manipal 1
8
3
 Change the colors of nodes 5, 7 and 8.

28/11/2025 School of Computer Engineering, MIT, Manipal 1

8
4
 • Move x up to its grandparent, 7.

• x's parent (2) is still red, so this isn't a red-black tree yet.

• Mark the uncle, y.

• In this case, the uncle is black, so we have case 2 .

28/11/2025 School of Computer Engineering, MIT, Manipal 1

8
5
 Move x up and rotate left.

Still not a red-black tree... the uncle is black, but x's parent is
to the left .

28/11/2025 School of Computer Engineering, MIT, Manipal 1

8
6
 Change the colors of 7 and 11 and rotate right.

This is now a red-black tree,

28/11/2025 School of Computer Engineering, MIT, Manipal 1

8
7