Trees

Tree is a nonlinear data structure and is used to represent data containing in hierarchical
relationship between an element or item. Many mathematical expressions can be represented
by the trees. General tree may have N number of disjoint successor nodes. A tree is a graph
containing no loops or cycle.

Why Tree Data Structure?

Other data structures such as arrays, linked list, stack, and queue are linear data structures that
store data sequentially. In order to perform any operation in a linear data structure, the time
complexity increases with the increase in the data size. But, it is not acceptable in today's
computational world.
Different tree data structures allow quicker and easier access to the data as it is a non-linear
data structure.

Basic Terminologies In Tree Data Structure:

Node

A node is an entity that contains a key or value and pointers to its child nodes.

The last nodes of each path are called leaf nodes or external nodes that do not contain a
link/pointer to child nodes.
The node having at least a child node is called an internal node.
Edge

It is the link between any two nodes.

Nodes and edges of a tree
Root

It is the topmost node of a tree.

Height of a Node

The height of a node is the number of edges from the node to the deepest leaf (ie. the longest
path from the node to a leaf node).

Depth of a Node

The depth of a node is the number of edges from the root to the node.

Height of a Tree

The height of a Tree is the height of the root node or the depth of the deepest node.

Height and depth of each node in a tree

Degree of a Node

The degree of a node is the total number of branches of that node.

Path: Sequence of consecutive edges from source and to the destination is called path.

path between node 1 and 7 is (1,3),(3,7)

Length of path:

Tree Applications
 Binary Search Trees(BSTs) are used to quickly check whether an element is present in
a set or not.
 Heap is a kind of tree that is used for heap sort.
 A modified version of a tree called Tries is used in modern routers to store routing
information.
 Most popular databases use B-Trees and T-Trees, which are variants of the tree
structure we learned above to store their data
 Compilers use a syntax tree to validate the syntax of every program you write.

Basic Terminologies In Tree Data Structure:

 Parent Node: The node which is a predecessor of a node

is called the parent node of that node. {B} is the parent
node of {D, E}.
 Child Node: The node which is the immediate successor of
a node is called the child node of that node. Examples: {D,
E} are the child nodes of {B}.
 Root Node: The topmost node of a tree or the node which
does not have any parent node is called the root node.
{A} is the root node of the tree. A non-empty tree must
contain exactly one root node and exactly one path from
the root to all other nodes of the tree.
 Leaf Node or External Node: The nodes which do not
have any child nodes are called leaf nodes. {K, L, M, N,
O, P} are the leaf nodes of the tree.
 Ancestor of a Node: Any predecessor nodes on the path
of the root to that node are called Ancestors of that
node. {A,B} are the ancestor nodes of the node {E}
 Descendant: Any successor node on the path from the
leaf node to that node. {E,I} are the descendants of the
node {B}.
 Sibling: Children of the same parent node are called
siblings. {D,E} are called siblings.
 Level of a node: The count of edges on the path from the
root node to that node. The root node has level 0.
 Internal node: A node with at least one child is called
Internal Node.
 Neighbour of a Node: Parent or child nodes of that node
are called neighbors of that node.
 Subtree: Any node of the tree along with its descendant.
Example of Tree data structure

Here,
Node 1 is the root node
1 is the parent of 2 and 3
2 and 3 are the siblings
4, 5, 6, and 7 are the leaf nodes
Types of Tree data structures:
Types of Trees in Data Structure based on the number of children

Binary tree: In a binary tree, each node can have a maximum of two children linked to it.
Some common types of binary trees include full binary trees, complete binary trees, balanced
binary trees, and degenerate or pathological binary trees.
Ternary Tree: A Ternary Tree is a tree data structure in which each node has at most three
child nodes, usually distinguished as “left”, “mid” and “right”.
N-ary Tree or Generic Tree: Generic trees are a collection of nodes where each node is a data
structure that consists of records and a list of references to its children (duplicate references
are not allowed). Unlike the linked list, each node stores the address of multiple nodes.

Binary Tree
The Binary tree means that the node can have maximum two children. Here, binary name
itself suggests that 'two'; therefore, each node can have either 0, 1 or 2 children.
Example:

The above tree is a binary tree because each node contains the utmost
two children. The logical representation of the above tree is given below:
In the above tree, node 1 contains two pointers, i.e., left and a right pointer
pointing to the left and right node respectively. The node 2 contains both the
nodes (left and right node); therefore, it has two pointers (left and right). The
nodes 3, 5 and 6 are the leaf nodes, so all these nodes contain NULL pointer on
both left and right parts.

Properties of Binary Tree

o At each level of i, the maximum number of nodes is 2i.
o The height of the tree is defined as the longest path from the root node to the leaf
node. The tree which is shown above has a height equal to 3. Therefore, the maximum
number of nodes at height 3 is equal to (1+2+4+8) = 15. In general, the maximum
number of nodes possible at height h is (20 + 21 + 22+….2h) = 2h+1 -1.
o The minimum number of nodes possible at height h is equal to h+1.
o If the number of nodes is minimum, then the height of the tree would be maximum.
Conversely, if the number of nodes is maximum, then the height of the tree would be
minimum.
If there are 'n' number of nodes in the binary tree.
The minimum height can be computed as:
As we know that,
n = 2h+1 -1
n+1 = 2h+1
Taking log on both the sides,
log2(n+1) = log2(2h+1)
log2(n+1) = h+1
h = log2(n+1) - 1
The maximum height can be computed as:
As we know that,
n = h+1
h= n-1
We can visit or traverse the tree. The process of visiting the nodes is known as tree traversal.
There are three types traversals used to visit a node:
o Inorder traversal or Depth first order
o Preorder traversal or Symmetric order
o Postorder traversal
o Level order
1] Pre-order (NODE-LEFT-RIGHT) Traversing:(method)
In pre-order, the traversing is performed as given below:
(a) Process the root node say T. (N)
(b) Traverse the left subtree of T in pre-order (L)
(c) Traverse the right subtree of T in pre-order. (R)
Algorithm:
1. Step 1: Repeat Steps 2 to 4 while TREE != NULL
2. Step 2: Write TREE -> DATA
3. Step 3: PREORDER(TREE -> LEFT)
4. Step 4: PREORDER(TREE -> RIGHT)
5. [END OF LOOP]
6. Step 5: END

Example of preorder traversal

Now, let's see an example of preorder traversal. It will be easier to understand the process of
preorder traversal using an example.

The nodes with yellow color are not visited yet. Now, we will traverse the nodes of the above
tree using preorder traversal.
o Start with the root node 40. First, print 40 and then recursively traverse the left
subtree.

o Now, move to the left subtree. For left subtree, the root node is 30. Print 30, and move
towards the left subtree of 30.

o In left subtree of 30, there is an element 25, so print 25, and traverse the left subtree of
25.

o In left subtree of 25, there is an element 15, and 15 has no

subtree. So, print 15, and move to the right subtree of 25.
In right subtree of 25, there is 28, and 28 has no subtree. So, print 28, and move to the right subtree
of 30.

o In right subtree of 30, there is 35 that has no subtree. So print 35, and traverse the right
subtree of 40.

o In the right subtree of 40, there is 50. Print 50, and traverse the left subtree of 50.
o In the left subtree of 50, there is 45 that do not have any child. So, print 45, and traverse the
right subtree of 50.

o In right subtree of 50, there is 60. Print 60 and traverse the left subtree of 60.

o In the left subtree of 60, there is 55 that does not have any child. So, print 55 and move to the
right subtree of 60.

o In the right subtree of 60, there is 70 that do not have any child. So, print 70 and stop the
process.

After the completion of preorder traversal, the final output is -

40, 30, 25, 15, 28, 35, 50, 45, 60, 55, 70
Complexity of Preorder traversal
The time complexity of preorder traversal is O(n), where 'n' is the size of binary tree.

Whereas, the space complexity of preorder traversal is O (1), if we do not consider the stack
size for function calls. Otherwise, the space complexity of preorder traversal is O(h), where
'h' is the height of the tree.

2] In-order traversal (LEFT-NODE-RIGHT) Traversing(method):

In In-order traversal, the traversing is performed as given below:
(a) Traverse the left subtree of T in In-order. (L)
(b) Process the root T. (N)
(c) Traverse the right subtree of T in in-order. (R)
Algorithm:
1.Repeat steps 2 to 4 until Tree!=null
2.Inorder(Tree->left)
3. Write Tree->data
4. Inorder(Tree->right)
End of loop
5.End

Example of inorder traversal

Now, let's see an example of inorder traversal. It will be easier to understand the procedure of
inorder traversal using an example.

The nodes with yellow color are not visited yet. Now, we will traverse the nodes of the above
tree using inorder traversal.

Here, 40 is the root node. We move to the left subtree of 40, that is 30, and it also has subtree
25, so we again move to the left subtree of 25 that is 15. Here, 15 has no subtree, so print
15 and move towards its parent node, 25.

o Now, print 25 and move to the right subtree of 25.

o Now, print 28 and move to the root node of 25 that is 30.

o So, left subtree of 30 is visited. Now, print 30 and move to the right child of 30.
o Now, print 35 and move to the root node of 30

o Now, print root node 40 and move to its right subtree.

o Now recursively traverse the right subtree of 40 that is 50.

50 have subtree so first traverse the left subtree of 50 that is 45. 45 has no children,
so print 45 and move to its root node.

o Now print 50 and move to the right subtree of 50 that is 60.

o Now recursively traverse the right subtree of 50 that is 60. 60 have subtree so first
traverse the left subtree of 60 that is 55. 55 has no children, so print 55 and move to
its root node.
o Now print 60 and move to the right subtree of 60 that is 70.

o Now print 70.

After the completion of inorder traversal, the final output is -

{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}

Complexity of Inorder traversal

The time complexity of Inorder traversal is O(n), where 'n' is the size of binary tree.
Whereas, the space complexity of inorder traversal is O(1), if we do not consider the stack size for
function calls. Otherwise, the space complexity of inorder traversal is O(h), where 'h' is the height of
tree.
3] Post-order traversal (LEFT-RIGHT-NODE) traversing:
In post-order, traversing is performed as given below:
(a) Traverse the left subtree of T in post order. (L)
(b) Traverse the right subtree of T in post order. (R)
(c) Process the root T. (N)

Algorithm:
1. Step 1: Repeat Steps 2 to 4 while TREE != NULL
2. Step 2: POSTORDER(TREE -> LEFT)
3. Step 3: POSTORDER(TREE -> RIGHT)
4. Step 4: Write TREE -> DATA
5. [END OF LOOP]
6. Step 5: END

Example of postorder traversal

Now, let's see an example of postorder traversal. It will be easier to understand the process of
postorder traversal using an example.

The nodes with yellow color are not visited yet. Now, we will traverse the nodes of above
tree using postorder traversal.

Here, 40 is the root node. We first visit the left subtree of 40, i.e., 30. Node 30 will also traverse in
post order. 25 is the left subtree of 30, so it is also traversed in post order. Then 15 is the left subtree
of 25. But 15 has no subtree, so print 15 and move towards the right subtree of 25.
o 28 is the right subtree of 25, and it has no children. So, print 28.

o Now, print 25, and the postorder traversal for 25 is finished.

o Next, move towards the right subtree of 30. 35 is the right subtree of 30, and it has no
children. So, print 35.

o After that, print 30, and the postorder traversal for 30 is finished. So, the left subtree
of given binary tree is traversed.

o Now, move towards the right subtree of 40 that is 50, and it will also traverse in post order.
45 is the left subtree of 50, and it has no children. So, print 45 and move towards the
right subtree of 50.
o 60 is the right subtree of 50, which will also be traversed in post order. 55 is the left subtree
of 60 that has no children. So, print 55.

o Now, print 70, which is the right subtree of 60.

o Now, print 60, and the post order traversal for 60 is completed.

o Now, print 50, and the post order traversal for 50 is completed.

o At last, print 40, which is the root node of the given binary tree, and the post order
traversal for node 40 is completed.
The final output that we will get after postorder traversal is -

{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}

Complexity of Postorder traversal

The time complexity of postorder traversal is O(n), where 'n' is the size of
binary tree.

Whereas, the space complexity of postorder traversal is O(1), if we do not

consider the stack size for function calls. Otherwise, the space complexity
of postorder traversal is O(h), where 'h' is the height of tree.

4] Level order (Top-bottom, Left -Right) Traversing:

In a level order traversal, nodes are visited by level from top to bottom and within each level
elements are visited from left to right.
Consider the graph:

o Here we will traverse level by level that means all the nodes of level 0 will be
traversed first and then level 1 nodes and then level 2 and so on.
o So the first node that will be visited is 40 that is on level 0.(draw graph on each step)
o Next will be 30 and 50 that are on level 1.(draw graph and show nodes 30 and 40 are
visited)
o After that nodes 25, 35, 45 and 60 will be visited that are on level 2.(draw graph)
o Finally nodes 15, 28, 55 and 70 will be visited and the level order traversal output
will be:
40,30,50,25,35,45,60,15,28,55 and 70.

Binary Search Tree (BST):

A binary search tree follows some order to arrange the elements. In a Binary search tree, the
value of left node must be smaller than the parent node, and the value of right node must be
greater than the parent node. This rule is applied recursively to the left and right subtrees of
the root.
Let's understand the concept of Binary search tree with an example.

In the above figure, we can observe that the root node is 40, and all the nodes of the left
subtree are smaller than the root node, and all the nodes of the right subtree are greater than
the root node.

Similarly, we can see the left child of root node is greater than its left child and smaller than
its right child. So, it also satisfies the property of binary search tree. Therefore, we can say
that the tree in the above image is a binary search tree.

Suppose if we change the value of node 35 to 55 in the above tree, check whether the tree
will be binary search tree or not.

In the above tree, the value of root node is 40, which is greater than its left child 30 but
smaller than right child of 30, i.e., 55. So, the above tree does not satisfy the property of
Binary search tree. Therefore, the above tree is not a binary search tree.

[WHEN BI NARY TREE IS TRAVERSED USING IN ORDER TRAVERSAL THE

LIST CONTAIN SORTED ORDER].

Advantages of Binary search tree

 Searching an element in the Binary search tree is easy as we always have a hint that
which subtree has the desired element.
 As compared to array and linked lists, insertion and deletion operations are faster in
BST.

Example of creating a binary search tree

Now, let's see the creation of binary search tree using an example.

Suppose the data elements are - 45, 15, 79, 90, 10, 55, 12, 20, 50
 First, we have to insert 45 into the tree as the root of the tree.
 Then, read the next element; if it is smaller than the root node, insert it as the root of
the left subtree, and move to the next element.
 Otherwise, if the element is larger than the root node, then insert it as the root of the
right subtree.

Now, let's see the process of creating the Binary search tree using the given data element. The
process of creating the BST is shown below -

Step 1 - Insert 45.

Step 2 - Insert 15.

As 15 is smaller than 45, so insert it as the root node of the left subtree.

Step 3 - Insert 79.

As 79 is greater than 45, so insert it as the root node of the right subtree.

Step 4 - Insert 90.

90 is greater than 45 and 79, so it will be inserted as the right subtree of 79.
Step 5 - Insert 10.

10 is smaller than 45 and 15, so it will be inserted as a left subtree of 15.

Step 6 - Insert 55.

55 is larger than 45 and smaller than 79, so it will be inserted as the left subtree of 79.

Step 7 - Insert 12.

12 is smaller than 45 and 15 but greater than 10, so it will be inserted as the right subtree of
10.

Step 8 - Insert 20.

20 is smaller than 45 but greater than 15, so it will be inserted as the right subtree of 15.
Step 9 - Insert 50.

50 is greater than 45 but smaller than 79 and 55. So, it will be inserted as a left subtree of 55.

Now, the creation of binary search tree is completed. After that, let's move towards the
operations that can be performed on Binary search tree.

We can perform insert, delete and search operations on the binary search tree.

Searching in Binary search tree

Searching means to find or locate a specific element or node in a data structure. In Binary
search tree, searching a node is easy because elements in BST are stored in a specific order.
The steps of searching a node in Binary Search tree are listed as follows -

1. First, compare the element to be searched with the root element of the tree.
2. If root is matched with the target element, then return the node's location.
3. If it is not matched, then check whether the item is less than the root element, if it is
smaller than the root element, then move to the left subtree.
4. If it is larger than the root element, then move to the right subtree.
5. Repeat the above procedure recursively until the match is found.
6. If the element is not found or not present in the tree, then return NULL.

Now, let's understand the searching in binary tree using an example. We are taking the binary
search tree formed above. Suppose we have to find node 20 from the below tree.

Step1:
Step2:

Step3:

Now, let's see the algorithm to search an element in the Binary search tree.

Algorithm to search an element in Binary search tree

1. Search (root, item)

2. Step 1 - if (item = root → data) or (root = NULL)
3. return root
4. else if (item < root → data)
5. return Search(root → left, item)
6. else
7. return Search(root → right, item)
8. END if
9. Step 2 - END
Deletion in Binary Search tree

In a binary search tree, we must delete a node from the tree by keeping in mind that the
property of BST is not violated. To delete a node from BST, there are three possible
situations occur -

 The node to be deleted is the leaf node, or,

 The node to be deleted has only one child, and,
 The node to be deleted has two children

We will understand the situations listed above in detail.

When the node to be deleted is the leaf node

It is the simplest case to delete a node in BST. Here, we have to replace the leaf node with
NULL and simply free the allocated space.

We can see the process to delete a leaf node from BST in the below image. In below image,
suppose we have to delete node 90, as the node to be deleted is a leaf node, so it will be
replaced with NULL, and the allocated space will free.

When the node to be deleted has only one child

In this case, we have to replace the target node with its child, and then delete the child node.
It means that after replacing the target node with its child node, the child node will now
contain the value to be deleted. So, we simply have to replace the child node with NULL and
free up the allocated space.

We can see the process of deleting a node with one child from BST in the below image. In
the below image, suppose we have to delete the node 79, as the node to be deleted has only
one child, so it will be replaced with its child 55.

So, the replaced node 79 will now be a leaf node that can be easily deleted.
When the node to be deleted has two children

This case of deleting a node in BST is a bit complex among other two cases. In such a case,
the steps to be followed are listed as follows -

 First, find the inorder successor of the node to be deleted.

 After that, replace that node with the inorder successor until the target node is placed
at the leaf of tree.
 And at last, replace the node with NULL and free up the allocated space.

The inorder successor is required when the right child of the node is not empty. We can
obtain the inorder successor by finding the minimum element in the right child of the node.

We can see the process of deleting a node with two children from BST in the below image. In
the below image, suppose we have to delete node 45 that is the root node, as the node to be
deleted has two children, so it will be replaced with its inorder successor. Now, node 45 will
be at the leaf of the tree so that it can be deleted easily.

Now let's understand how insertion is performed on a binary search tree.

Insertion in Binary Search tree

A new key in BST is always inserted at the leaf. To insert an element in BST, we have to start
searching from the root node; if the node to be inserted is less than the root node, then search
for an empty location in the left subtree. Else, search for the empty location in the right
subtree and insert the data. Insert in BST is similar to searching, as we always have to
maintain the rule that the left subtree is smaller than the root, and right subtree is larger than
the root.

Now, let's see the process of inserting a node into BST using an example.

The complexity of the Binary Search tree

Let's see the time and space complexity of the Binary search tree. We will see the time
complexity for insertion, deletion, and searching operations in best case, average case, and
worst case.

1. Time Complexity

Best case time Average case time Worst case time

Operations
complexity complexity complexity
Insertion O(log n) O(log n) O(n)
Deletion O(log n) O(log n) O(n)
Search O(log n) O(log n) O(n)

Where 'n' is the number of nodes in the given tree.

2. Space Complexity
Operations Space complexity
Insertion O(n)
Deletion O(n)

Search O(n)

 The space complexity of all operations of Binary search tree is O(n).

AVL OR HEIGHT BALANCED TREE:

AVL Tree is invented by GM Adelson - Velsky and EM Landis in 1962. The tree is named
AVL in honour of its inventors.

AVL Tree can be defined as height balanced binary search tree in which each node is
associated with a balance factor which is calculated by subtracting the height of its right sub-
tree from that of its left sub-tree.

Tree is said to be balanced if balance factor of each node is in between -1 to 1, otherwise, the
tree will be unbalanced and need to be balanced.

Balance Factor (k) = height (left(k)) - height (right(k))

If balance factor of any node is 1, it means that the left sub-tree is one level higher than the
right sub-tree.

If balance factor of any node is 0, it means that the left sub-tree and right sub-tree contain
equal height.

If balance factor of any node is -1, it means that the left sub-tree is one level lower than the
right sub-tree.

An AVL tree is given in the following figure. We can see that, balance factor associated with
each node is in between -1 and +1. therefore, it is an example of AVL tree.
25 is having balance factor 0 because there is no left child and no right child so 0-0=0.

Similarly 50 having balance factor -1 as there is one left child and on right side we have 2 so
the balance factor is 1-2=-1. And so on.

Complexity

Algorithm Average case Worst case

Space o(n) o(n)
Search o(log n) o(log n)
Insert o(log n) o(log n)
Delete o(log n) o(log n)

Operations on AVL tree

Due to the fact that, AVL tree is also a binary search tree therefore, all the operations are
performed in the same way as they are performed in a binary search tree. Searching and
traversing do not lead to the violation in property of AVL tree. However, insertion and
deletion are the operations which can violate this property and therefore, they need to be
revisited.

SN Operation Description
Insertion in AVL tree is performed in the same way as it is performed in a
binary search tree. However, it may lead to violation in the AVL tree property
1 Insertion
and therefore the tree may need balancing. The tree can be balanced by
applying rotations.
Deletion can also be performed in the same way as it is performed in a binary
2 Deletion search tree. Deletion may also disturb the balance of the tree therefore,
various types of rotations are used to rebalance the tree.

Why AVL Tree?

AVL tree controls the height of the binary search tree by not letting it to be skewed. The time
taken for all operations in a binary search tree of height h is O(h). However, it can be
extended to O(n) if the BST becomes skewed (i.e. worst case). By limiting this height to log
n, AVL tree imposes an upper bound on each operation to be O(log n) where n is the number
of nodes.

AVL Rotations

We perform rotation in AVL tree only in case if Balance Factor is other than -1, 0, and 1.
There are basically four types of rotations which are as follows:

1. L L rotation: Inserted node is in the left subtree of left subtree of A

2. R R rotation : Inserted node is in the right subtree of right subtree of A
3. L R rotation : Inserted node is in the right subtree of left subtree of A
4. R L rotation : Inserted node is in the left subtree of right subtree of A

Where node A is the node whose balance Factor is other than -1, 0, 1.

The first two rotations LL and RR are single rotations and the next two rotations LR and RL
are double rotations. For a tree to be unbalanced, minimum height must be at least 2, Let us
understand each rotation

1. RR Rotation

When BST becomes unbalanced, due to a node is inserted into the right subtree of the right
subtree of A, then we perform RR rotation, RR rotation is an anticlockwise rotation, which is
applied on the edge below a node having balance factor -2

In above example, node A has balance factor -2 because a node C is inserted in the right
subtree of A right subtree. We perform the RR rotation on the edge below A.

2. LL Rotation

When BST becomes unbalanced, due to a node is inserted into the left subtree of the left
subtree of C, then we perform LL rotation, LL rotation is clockwise rotation, which is applied
on the edge below a node having balance factor 2.
Let us understand each and every step very clearly:

State Action

A node B has been inserted into the right subtree of A the left subtree of C,
because of which C has become an unbalanced node having balance factor 2.
This case is L R rotation where: Inserted node is in the right subtree of left
subtree of C

As LR rotation = RR + LL rotation, hence RR (anticlockwise) on subtree rooted

at A is performed first. By doing RR rotation, node A, has become the left
subtree of B.

After performing RR rotation, node C is still unbalanced, i.e., having balance

factor 2, as inserted node A is in the left of left of C
Now we perform LL clockwise rotation on full tree, i.e. on node C. node C has
now become the right subtree of node B, A is left subtree of B

Balance factor of each node is now either -1, 0, or 1, i.e. BST is balanced now.

4. RL Rotation

As already discussed, that double rotations are bit tougher than single rotation which has
already explained above. R L rotation = LL rotation + RR rotation, i.e., first LL rotation is
performed on subtree and then RR rotation is performed on full tree, by full tree we mean the
first node from the path of inserted node whose balance factor is other than -1, 0, or 1.

State Action

A node B has been inserted into the left subtree of C the right subtree of A,
because of which A has become an unbalanced node having balance factor - 2.
This case is RL rotation where: Inserted node is in the left subtree of right
subtree of A

As RL rotation = LL rotation + RR rotation, hence, LL (clockwise) on subtree

rooted at C is performed first. By doing RR rotation, node C has become the right
subtree of B.

After performing LL rotation, node A is still unbalanced, i.e. having balance factor
-2, which is because of the right-subtree of the right-subtree node A.
Now we perform RR rotation (anticlockwise rotation) on full tree, i.e. on node A.
node C has now become the right subtree of node B, and node A has become
the left subtree of B.

Balance factor of each node is now either -1, 0, or 1, i.e., BST is balanced now.

Q: Construct an AVL tree having the following elements

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

1. Insert H, I, J

On inserting the above elements, especially in the case of H, the BST becomes unbalanced as
the Balance Factor of H is -2. Since the BST is right-skewed, we will perform RR Rotation
on node H.

The resultant balance tree is:

2. Insert B, A
On inserting the above elements, especially in case of A, the BST becomes unbalanced as the
Balance Factor of H and I is 2, we consider the first node from the last inserted node i.e. H.
Since the BST from H is left-skewed, we will perform LL Rotation on node H.

The resultant balance tree is:

3. Insert E

On inserting E, BST becomes unbalanced as the Balance Factor of I is 2, since if we travel

from E to I we find that it is inserted in the left subtree of right subtree of I, we will perform
LR Rotation on node I. LR = RR + LL rotation

3 a) We first perform RR rotation on node B

The resultant tree after RR rotation is:

3b) We first perform LL rotation on the node I

The resultant balanced tree after LL rotation is:

4. Insert C, F, D

On inserting C, F, D, BST becomes unbalanced as the Balance Factor of B and H is -2, since
if we travel from D to B we find that it is inserted in the right subtree of left subtree of B, we
will perform RL Rotation on node I. RL = LL + RR rotation.

4a) We first perform LL rotation on node E

The resultant tree after LL rotation is:

4b) We then perform RR rotation on node B

The resultant balanced tree after RR rotation is:

5. Insert G

On inserting G, BST become unbalanced as the Balance Factor of H is 2, since if we travel

from G to H, we find that it is inserted in the left subtree of right subtree of H, we will
perform LR Rotation on node I. LR = RR + LL rotation.

5 a) We first perform RR rotation on node C

The resultant tree after RR rotation is:

5 b) We then perform LL rotation on node H

The resultant balanced tree after LL rotation is:

6. Insert K

On inserting K, BST becomes unbalanced as the Balance Factor of I is -2. Since the BST is
right-skewed from I to K, hence we will perform RR Rotation on the node I.

The resultant balanced tree after RR rotation is:

7. Insert L

On inserting the L tree is still balanced as the Balance Factor of each node is now either, -1,
0, +1. Hence the tree is a Balanced AVL tree
In above example, node C has balance factor 2 because a node A is inserted in the left subtree
of C left subtree. We perform the LL rotation on the edge below A.

3. LR Rotation

Double rotations are bit tougher than single rotation which has already explained above. LR
rotation = RR rotation + LL rotation, i.e., first RR rotation is performed on subtree and then
LL rotation is performed on full tree, by full tree we mean the first node from the path of
inserted node whose balance factor is other than -1, 0, or 1.

B Tree

B Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of order
m can have at most m-1 keys and m children. One of the main reason of using B tree is its
capability to store large number of keys in a single node and large key values by keeping the
height of the tree relatively small.

A B tree of order m contains all the properties of an M way tree. In addition, it contains the
following properties.

1. Every node in a B-Tree contains at most m children.

2. Every node in a B-Tree except the root node and the leaf node contain at least m/2
children.
3. The root nodes must have at least 2 nodes.
4. All leaf nodes must be at the same level.

It is not necessary that, all the nodes contain the same number of children but, each node
must have m/2 number of nodes.

A B tree of order 4 is shown in the following image.

While performing some operations on B Tree, any property of B Tree may violate such as
number of minimum children a node can have. To maintain the properties of B Tree, the tree
may split or join.

Operations

Searching :

Searching in B Trees is similar to that in Binary search tree. For example, if we search for an
item 49 in the following B Tree. The process will something like following :

1. Compare item 49 with root node 78. since 49 < 78 hence, move to its left sub-tree.
2. Since, 40<49<56, traverse right sub-tree of 40.
3. 49>45, move to right. Compare 49.
4. match found, return.

Searching in a B tree depends upon the height of the tree. The search algorithm takes O(log
n) time to search any element in a B tree.

Inserting

Insertions are done at the leaf node level. The following algorithm needs to be followed in
order to insert an item into B Tree.

1. Traverse the B Tree in order to find the appropriate leaf node at which the node can
be inserted.
2. If the leaf node contain less than m-1 keys then insert the element in the increasing
order.
3. Else, if the leaf node contains m-1 keys, then follow the following steps.
o Insert the new element in the increasing order of elements.
o Split the node into the two nodes at the median.
o Push the median element upto its parent node.
o If the parent node also contain m-1 number of keys, then split it too by
following the same steps.

Example:

Insert the node 8 into the B Tree of order 5 shown in the following image.
8 will be inserted to the right of 5, therefore insert 8.

The node, now contain 5 keys which is greater than (5 -1 = 4 ) keys. Therefore split the node
from the median i.e. 8 and push it up to its parent node shown as follows.

Deletion

Deletion is also performed at the leaf nodes. The node which is to be deleted can either be a
leaf node or an internal node. Following algorithm needs to be followed in order to delete a
node from a B tree.

1. Locate the leaf node.

2. If there are more than m/2 keys in the leaf node then delete the desired key from the
node.
3. If the leaf node doesn't contain m/2 keys then complete the keys by taking the element
from eight or left sibling.
o If the left sibling contains more than m/2 elements then push its largest
element up to its parent and move the intervening element down to the node
where the key is deleted.
o If the right sibling contains more than m/2 elements then push its smallest
element up to the parent and move intervening element down to the node
where the key is deleted.
4. If neither of the sibling contain more than m/2 elements then create a new leaf node
by joining two leaf nodes and the intervening element of the parent node.
5. If parent is left with less than m/2 nodes then, apply the above process on the parent
too.
If the the node which is to be deleted is an internal node, then replace the node with its in-
order successor or predecessor. Since, successor or predecessor will always be on the leaf
node hence, the process will be similar as the node is being deleted from the leaf node.

Example 1

Delete the node 53 from the B Tree of order 5 shown in the following figure.

53 is present in the right child of element 49. Delete it.

Now, 57 is the only element which is left in the node, the minimum number of elements that
must be present in a B tree of order 5, is 2. it is less than that, the elements in its left and right
sub-tree are also not sufficient therefore, merge it with the left sibling and intervening
element of parent i.e. 49.

The final B tree is shown as follows.

Application of B tree

B tree is used to index the data and provides fast access to the actual data stored on the disks
since, the access to value stored in a large database that is stored on a disk is a very time
consuming process.
Searching an un-indexed and unsorted database containing n key values needs O(n) running
time in worst case. However, if we use B Tree to index this database, it will be searched in
O(log n) time in worst case.

Threaded binary tree:

What do you mean by Threaded Binary Tree?

In the linked representation of binary trees, more than one half of the link fields contain
NULL values which results in wastage of storage space. If a binary tree consists of n nodes
then n+1 link fields contain NULL values. So in order to effectively manage the space, a
method was devised by Perlis and Thornton in which the NULL links are replaced with
special links known as threads. Such binary trees with threads are known as threaded binary
trees. Each node in a threaded binary tree either contains a link to its child node or thread to
other nodes in the tree.

Types of Threaded Binary Tree

There are two types of threaded Binary Tree:

 One-way threaded Binary Tree

 Two-way threaded Binary Tree

One-way threaded Binary trees:

In one-way threaded binary trees, a thread will appear either in the right or left link field of a
node. If it appears in the right link field of a node then it will point to the next node that will
appear on performing in order traversal. Such trees are called Right threaded binary trees.
If thread appears in the left field of a node then it will point to the nodes inorder predecessor.
Such trees are called Left threaded binary trees. Left threaded binary trees are used less
often as they don't yield the last advantages of right threaded binary trees. In one-way
threaded binary trees, the right link field of last node and left link field of first node contains
a NULL. In order to distinguish threads from normal links they are represented by dotted
lines.

The above figure shows the inorder traversal of this binary tree yields D, B, E, A, C, F. When
this tree is represented as a right threaded binary tree, the right link field of leaf node D which
contains a NULL value is replaced with a thread that points to node B which is the inorder
successor of a node D. In the same way other nodes containing values in the right link field
will contain NULL value.

Two-way threaded Binary Trees:

In two-way threaded Binary trees, the right link field of a node containing NULL values is
replaced by a thread that points to nodes inorder successor and left field of a node containing
NULL values is replaced by a thread that points to nodes inorder predecessor.
The above figure shows the inorder traversal of this binary tree yields D, B, E, G, A, C, F. If
we consider the two-way threaded Binary tree, the node E whose left field contains NULL is
replaced by a thread pointing to its inorder predecessor i.e. node B. Similarly, for node G
whose right and left linked fields contain NULL values are replaced by threads such that right
link field points to its inorder successor and left link field points to its inorder predecessor. In
the same way, other nodes containing NULL values in their link fields are filled with threads.

In the above figure of two-way threaded Binary tree, we noticed that no left thread is possible
for the first node and no right thread is possible for the last node. This is because they don't
have any inorder predecessor and successor respectively. This is indicated by threads
pointing nowhere. So in order to maintain the uniformity of threads, we maintain a special
node called the header node. The header node does not contain any data part and its left link
field points to the root node and its right link field points to itself. If this header node is
included in the two-way threaded Binary tree then this node becomes the inorder predecessor
of the first node and inorder successor of the last node. Now threads of left link fields of the
first node and right link fields of the last node will point to the header node.

Advantages of Threaded Binary Tree:

 In threaded binary tree, linear and fast traversal of nodes in the tree so there is no
requirement of stack. If the stack is used then it consumes a lot of memory and time.
 It is more general as one can efficiently determine the successor and predecessor of
any node by simply following the thread and links. It almost behaves like a circular
linked list.

Disadvantages of Threaded Binary Tree:

 When implemented, the threaded binary tree needs to maintain the extra information
for each node to indicate whether the link field of each node points to an ordinary
node or the node's successor and predecessor.
 Insertion into and deletion from a threaded binary tree are more time consuming since
both threads and ordinary links need to be maintained.