UNIT III TREES

TREES

A tree is a finite set of one or more nodes such that it contains a root node and several disjoint
sets.

4.1 Binary Tree:

A binary tree is a finite set of elements i.e., either empty (or) is partitioned into three disjoint
sub-sets. The first sub-set contains a single element called the root of the tree. The other two
subsets are themselves binary trees; called the left and right sub trees of the original tree. The
left (or) right sub tree can be empty each element of a binary tree is called a node of the tree.

Level 0 A

Level 1 B C

Level 2 D E F

Level 3 G H I Fig: Binary Tree

➢ Root (A) is a unique node in the tree to which further sub trees are attached. Its left sub tree
is rooted at B and its right sub tree is rooted at C. This is indicated by the two branches from
A to B on the left and to A to C on the right. The absence of a branch indicates an empty sub
tree.
➢ The total number of sub-trees attached to that node is called its degree. The degree of A is 2.
Nodes that have degree zero are called leaf (or) terminal nodes (or) external nodes (or)
leaves.
➢ Non-terminals are the nodes other than root node and leaf nodes.
➢ The node having further sub-branches is called parent node. In above figure, A is parent of B
and C. sub-branches are called as children. Children of the same parent are said to be siblings.

DATA STRUCTURES
UNIT III TREES

➢ The root node is always considered at level 0. The height (or) depth of a tree is defined to be
the maximum level of any node in the tree. Thus the depth of tree in figure is 3.

4.2 Types of Binary Tree:

1. Strictly binary tree

2. Complete binary tree
3. Skewed binary tree
4. Full binary tree

1. Strictly binary tree: - The binary tree is said to be strictly binary tree, if a binary tree of depth
K having 2K-1 nodes.
1
E.g. Here No: of Nodes = 23-1 = 7
2 3

4 5 6 7

2. Complete binary tree: - A binary tree with n nodes and depth K is complete if its nodes
correspond to the nodes numbered from 1 to n in the full binary tree of depth K

2 3

4 5 6 7
Fig: - Complete BT
8 9
Here in complete binary tree, 1st we have to insert left child and the right child and again if we
want to insert new element, it must be left child of left child element (i.e., B's left child D).
3. Skewed binary tree: - The binary tree is said to be skewed binary tree, if each and every node
in the binary tree is having only one child i.e. either left (or) right.

DATA STRUCTURES
UNIT III TREES

1
1 (a) Skewed-left BT
2
2
(b) Skewed-right BT 3
3
4
4

4. Full binary tree: - A binary tree is said to be full binary tree if every non-leaf node in a binary
tree has non- empty left and right sub-tree.
1

2 3

4 5

Fig: - Strictly BT
6 7

4.3 Properties of a Binary Tree: -

1. The maximum number of nodes on level L of a binary tree is 2L, L>=0.

2. The maximum number of nodes in a binary tree of depth h is 2h+1-1, h>=0.
3. For any non-empty binary tree, T, if n0 is the number of leaf nodes and n2 is the number of
nodes of degree 2, then n0= n2+1.
1
Example: The following 3 steps illustrate the properties of a BT:
2 3
1. Maximum no of nodes on level 3 is = 23= 8.
On level 0, the maximum no of nodes = 20=1. 4 5 6 7

On level 1, the maximum no of nodes = 21=.2 8 9

2. No: of levels = 3 Fig: Binary Tree

Maximum no of nodes = 23+1-1 = 15
For depth 1, Maximum no: of nodes = 21+1-1= 3

DATA STRUCTURES
UNIT III TREES

For depth 2, Maximum no: of nodes = 22+1-1 = 7

3. From the figure n0 = 5 (degree 0 nodes);

n2 = 4 (degree 2 nodes);
n0 = n2+1
5=4+1
5=5

4.4 Representation of binary tree in memory:-

The structure of each node of a binary tree contains the data field and two fields for the left child
and for the right child.
Left Data Right

(a) Node of a binary tree

The structure that defines a node of a binary tree is as follows:-

struct binary-tree
{
struct binary-tree *left,
int data,
struct binary-tree *right,
};

There are two ways by which we can represent a binary tree.

a) Linked representation of a binary tree

b) Array representation of a binary tree

(a) Linked representation of a binary tree:-

Binary tree can be represented by links, where each node contains the address of the left child
and the right child. The leaf nodes contain a null value in its link fields, as there is no child to a

DATA STRUCTURES
UNIT III TREES

leaf node. So nodes contain a null value in its left (or) right link field because the respective child
of that particular node could be empty.

B C

D E F G

H
(a) Binary Tree

B C

N D N E N N F N N G N

N H N
(b) Linked List Representation of BT

In the above figure (b), the link fields of a node C contain the address of the nodes F and G. The
left field of node E contains the address of the node H. Similarly the right link contains a NULL
value as there is only one (left) child for node E. The nodes D, F, G and H contain a NULL value in
both their link fields, as these are the leaf nodes.
(b) Array Representation of Binary Trees: - When a binary tree is represented by arrays three
separate arrays are required. One array ARR stores the data fields of the trees. The other two
arrays LC and RC represent the left child and right child of the nodes. The following figure shows
three arrays, which represents the binary tree that is shown in figure (a)
A B C D E F G \0 \0 H
ARR:

DATA STRUCTURES
UNIT III TREES

LC: 1 3 5 - 1 9 - 1 - 1 - 1 - 1 - 1

RC: 2 4 6 - 1 - 1 - 1 - 1 - 1 - 1 - 1

The array LC and RC contains the index of the array ARR where the data is present if the node
does not have any left child (or) right child then the element of the array LC (or) RC contains a
value -1.
The 0th element of the array ARR that contains the data is always the root node of the tree. Some
elements of the array ARR contain '\0' which represents an empty child.
Suppose we want to find the left and right child of the node E. Then we need to find the value
present at index 4 in array LC and RC. Since E is present at index 4 in the array ARR. The value
present at index 4 in the array LC is 9 which is the index position of node H in the array ARR. So,
the left child of node E is H .The right child of the node E is empty because the value present at
index 4 in the array RC is -1.
Abstract Data Type: The ADT Binary Tree is a finite set of nodes which is either empty or consists
of a data item (called the root) and two disjoint binary trees (called the left and right subtrees of
the root), together with a number of access procedures.
The Binary Tree is a more general ADT than the linear list: it allows one item to have two
immediate successors.
To give a formal definition of what a tree is, we say that a binary tree is a set of node which is
either empty, or is partitioned into three disjoint subsets: (i) a single node “r”, the root; and (ii)
two (possibly empty) sets that are binary trees, called the left and the right subtrees of r. Each
node in a binary tree has therefore no more than two children.
Evaluation of expressions is a typical application of binary trees.

4.5Binary Tree Traversals:

The traversal of a binary tree is to visit each node in the tree exactly once. Binary tree
traversal is useful in many applications. The order in which nodes of a linear list are visited
is clearly from 1st to last.
There are 3 types of traversals for traversing a binary tree:-

DATA STRUCTURES
UNIT III TREES

1. Inorder traversal
2. Pre-order traversal
3. Post-order traversal
In each of these methods nothing has to be done to traverse an empty binary tree. The functions
used to traverse a tree using these methods can be kept quite short by following recursive nature
of the binary tree.
Binary tree is recursive in that each sub-tree is a binary tree itself. Thus traversing a binary tree
involves visiting the root node and traversing its left and right sub-trees. The only difference
among the methods is the order in which these three operations are performed.
The following are algorithms for traversing a non-empty binary tree
(1) In-order recursive algorithm for BT:
I. traverse the left sub-tree in in-order
II. visit the root
III. traverse the right sub-tree in in-order
(2) Pre-order recursive algorithm for BT:
I. visit the root
II. traverse the left sub-tree in pre-order
III. traverse the right sub-tree in pre-order
(3) Post-order recursive algorithm for BT:
I. traverse the left sub-tree in post-order
II. traverse the right sub-tree in post -order
III. visit the root
A
Example: Construct the BT Traversals for the following BT
1. In-order traversal DBEAFCG B C
2. Pre-order traversal ABDECFG
D E F G
3. Post-order traversal DEBFGCA

4.6 Tree Traversals Using Stack:-

→In-order tree traversal using stack:-
DATA STRUCTURES
UNIT III TREES

Algorithm:-
1. First initialize the stack array to null and create a binary tree
2. Push the node to stack and find the left child and push it on to stack until left child is NULL
3. If the left child is NULL, pop the top element from stack.
4. Print the node and find the right child and go to step2
5. If the right child is NULL, pop the element from stack and go to step4
6. If both the right child and stack is NULL, then tree is traversal completely in in-order.
Example: - consider the following binary tree

2 3

Stack s is initialized to NULL 4 5

=>operation Stack[s] In-order
* push1 1
* find left child of 1
Push 2 1, 2
* find left child of 2
Push 4 1, 2, 4
* find left child of 4
NULL, so pop element from Stack [s] to In-order
Pop 1, 2 4
* find right child of 4
NULL, so pop element from Stack [s] to In-order
Pop 1 4, 2
* find right child of 2
Push 5 1, 5 4, 2

=>operation Stack[s] In-order

DATA STRUCTURES
UNIT III TREES

* find left child of 5

NULL, so pop element from Stack[s]
Pop 1 4, 2, 5
* find right child of 5
NULL, so pop element from Stack[s] to In-order
Pop --- 4, 2, 5, 1
* find right child of 1
Push 3 3 4, 2, 5, 1
* find left child of 3
NULL, so pop element from Stack [s] to In-order
Pop --- 4, 2, 5, 1, 3
* find right child of 3
NULL, so pop element from Stack [s] to In-order
Pop Stack is empty 4, 2, 5, 1, 3
Since both the right child and stack is empty this represents the end of in-order traversal using
stack.
Therefore, the in-order traversal for the given Binary Tree is 4, 2, 5, 1, 3.

→ Pre-order traversal using stacks: -

Algorithm:-

1. First create a binary tree and initialize Stack [s] to NULL

2. Push the node to Stack [s]
3. Pop the element from Stack [s]
4. If the node is not NULL, print the node and push the right child and left child on to Stack [s]
5. Repeat step3 and step4 until Stack [s] is empty.

This represents that the tree is completely traversal in pre-order traversal

DATA STRUCTURES
UNIT III TREES

Example: - consider an example to traverse the binary tree in pre-order traversal

2 3

4 5

=>operation stack[s] Pre-order

* Initialize Stack [s] to NULL
* Push 1 1
* Pop the node and is not NULL, so move the node to preorder and push the right child and left
child to Stack [s] [node (1) is not NULL]
3, 2 1
* Pop the node and is not NULL, so move the node to preorder and push the right child and left
child to Stack [s] [node (2) is not NULL]
3, 5, 4 1, 2
* Pop the node and is not NULL, so move the node to preorder and push the right child and left
child to Stack [s] [node (4) is not NULL]
3, 5, NULL, NULL 1, 2, 4
* Pop the node and is equal to NULL, so move to step3 [node is NULL]
3, 5, NULL 1, 2, 4
* Pop the node and is equal to NULL, so move to step3 [node is NULL]
3, 5 1, 2, 4
* Pop the node and is not NULL, so move the node to preorder and push the right child and left
child to Stack [s] [node (5) is not NULL]
3, NULL, NULL 1, 2, 4, 5
* Pop the node and is equal to NULL, so move to step3 [node is NULL]
3, NULL 1, 2, 4, 5
* Pop the node and is equal to NULL, so move to step3 [node is NULL]

DATA STRUCTURES
UNIT III TREES

3 1, 2, 4, 5

=>operation stack[s] Pre-order

* Pop the node and is not NULL, so move the node to preorder and push the right child and left
child to Stack [s] [node (3) is not NULL]
NULL, NULL 1, 2, 4, 5, 3
* Pop the node and is equal to NULL, so move to step3 [node is NULL]
NULL 1, 2, 4, 5, 3
* Pop the node and is equal to NULL, so move to step3 [node is NULL]
--- 1, 2, 4, 5, 3
* Pop the node since Stack is Empty. Thus the preorder traversal using stacks.
The Pre-order traversal for the above Binary Tree is: 1, 2, 4, 5, 3

→ Post-order traversal using stacks: -

Algorithm: -

1. First create a binary tree and initialize the Stack1 and Stack2 to NULL
2. Push the node to Stack1
3. Pop the node from the Stack1
4. If the node is not NULL, then
(a) Push it on to Stack2
(b) Push the left child to Stack1
(c) Push the right child to Stack1
5. Repeat step3 and 4 until Stack1 is empty
6. Then pop the elements from the Stack2 to output until Stack2 is empty

Thus pre-order traversal of binary tree using stacks.

Example: - consider the following example to traverse the binary tree in post-order traversal.

DATA STRUCTURES
UNIT III TREES

2 3

4 5

=>operation Stack1 [s] Stack2 [s]

* Push 1 to Stack1 1 ---
* Pop from Stack1 and node is not NULL, so push the node to Stack2 and push the left child and
right child to Stack1 [node (1) is not NULL]
2, 3 1
* Pop from Stack1 and node is not NULL, so push the node to Stack2 and push the left child and
right child to Stack1 [node (3) is not NULL]
2, NULL, NULL 1, 3
* Pop from Stack1 and node is NULL, so move to step3.
2, NULL 1, 3
* Pop from Stack1 and node is NULL, so move to step3.
2 1, 3
* Pop from Stack1 and node is not NULL, so push the node to Stack2 and push the left child and
right child to Stack1 [node (2) is not NULL]
4, 5 1, 3, 2
* Pop from Stack1 and node is not NULL, so push the node to Stack2 and push the left child and
right child to Stack1 [node (5) is not NULL]
4, NULL, NULL 1, 3, 2, 5
* Pop from Stack1 and node is NULL, so move to step3.
4, NULL 1, 3, 2, 5
* Pop from Stack1 and node is NULL, so move to step3.
4 1, 3, 2, 5
* Pop from Stack1 and node is not NULL, so push the node to Stack2 and push the left child and

DATA STRUCTURES
UNIT III TREES

right child to Stack1 [node (4) is not NULL]

NULL, NULL 1, 3, 2, 5, 4
* Pop from Stack1 and node is NULL, so move to step3.
NULL 1, 3, 2, 5, 4
* Pop from Stack1 and node is NULL, so move to step3.
---- 1, 3, 2, 5, 4
Since the Stack1 is empty, pop the element from Stack2 to Output. 4, 5, 2, 3, 1.
This represents the elements in post-order traversal of BT using Stacks.

4.7Reconstruction of a binary tree from inorder and preorder traversals: -

The binary tree can be reconstructed by using the sequence of in-order / preorder / post-order
traversal. We can construct a unique binary tree if the result of in-order and pre-order traversal
are available.
Consider the following set of in-order and pre-order traversal
1. In-order traversal: 4, 7, 2, 8, 5, 1, 6, 9, 3
2. Pre-order traversal: 1, 2, 4, 7, 5, 8, 3, 6, 9

Since, the first value in the pre-order traversal gives us the root of the binary tree. So the node
with data 1 becomes the root of the binary tree. In in-order traversal, initially the left sub-tree is
traversed then the root node and then the right sub-tree.so the data before 1 in the in-order list
forms the left sub-tree and the data after 1 in the in-order list forms the right sub-tree. The
following figure (a) shows the structure of tree after separating the tree in left and right sub-
trees.

In: 4, 7, 2, 8, 5 In: 6, 9, 3
Pre: 2, 4, 7, 5,8 Pre: 3, 6, 9

Figure (a)

DATA STRUCTURES
UNIT III TREES

Now consider the next data in pre-order list which is 2 i.e. 2 is the root of the sub tree. Hence the
data before 2 in the in-order list forms the left subtree of the node that contains a value 2. The
data that comes to the right of 2 in the in-order list forms the right sub-tree of the node with
value 2. The following figure shows the tree after expanding the left and right subtree of the node
2.
1
Figure (b) 2

In: 6, 9, 3
In: 4, 7 Pre: 3, 6, 9
In: 8, 5
Pre: 4, 7 Pre: 5, 8

Now the next data in pre-order list is 4, so the root node of the left sub-tree of the node that
contains a value 2 is 4. The data before 4 in the inorder list forms the left sub-tree of the node
that contains a value 4. But as there is no data present before 4 in inorder list forms, the left sub-
tree of the node with value 4 is empty. The data that comes to the right of 4 in the in-order list
forms the right sub-tree of the node 4. The following figure shows the binary tree after expanding
the left and right sub-tree of the node that contains a value 4.
1

2
In: 6, 9, 3
4 In: 8, 5 Pre: 3, 6, 9

Figure (c) Pre: 5,

8
In: 7
Pre: 7

DATA STRUCTURES
UNIT III TREES

Since, we are now left with only one value 7 in both the pre-order and in-order form we simply
represent it with a node as shown in figure.

In: 6, 9, 3
4 In: 8, 5 Pre: 3, 6, 9
Pre: 5,
7 8

Figure (d)

The above procedure is applied for each node and all data are picked from the pre-order list and
are placed their respective sub-tree are constructed as a result, the whale tree is constructed.
The following figures (e) to (i) shows each step of construction of nodes one by one.
1
1
2 In: 6, 9,
2 5
3
In: 6, 9, Pre: 3,
4
4 3 6, 9
5 Pre: 3, 8
6, 9 7
7
In: 8
Figure (e) Figure (f)
Pre: 8

1 1
1

2 3
2 3 2 3

4 5 6
4 5 4 5 6

7 8 In: 9
7 8 7 8 9
In: 6, 9 Pre:
Pre: 6, 9 9

Figure (g) Figure (h) Figure (i)

DATA STRUCTURES
UNIT III TREES

The figure (i) shows the binary tree, which is reconstructed from the given in-order and pre-order
traversal.
→ Reconstruction of binary tree from post-order and in-order traversal: -

1. In-order: 4, 7, 2, 8, 5, 1, 6, 9, 3
2. post-order: 7, 4, 8, 5, 2, 9, 6, 3, 1

Since, the last value in the postorder traversal gives us the root of the binary tree. In in-order
traversal, initially the left sub-tree is traversed, then the root node and then the right sub-tree.
So the data before 1 in the in-order list forms the left subtree.so the data before 1 in the in-order
list forms the left sub-tree and the data after 1 in the in-order list forms the right sub-tree. The
following figure (a) shows the structure of tree after separating the tree in left and right sub-
trees.
1

In: 4, 7, 2, 8, 5 In: 6, 9, 3
Post: 7, 4, 8, 5, 2 Post: 9, 6, 3

Figure (a)

Now consider the next last data in post-order list which is 2, i.e. 2 is the root node of the left sub-
tree. Hence the data before 2 in the in-order list forms the left sub-tree of the node that contains
a value 2. The data that comes to the right of 2 in the in-order list forms the right sub-tree of the
node with value 2. The following figure shows the tree after expanding the left and right sub-tree
of the node 2.

1
2

In: 6, 9, 3
In: 4, 7 Pre: 9, 6, 3
In: 8, 5
Post: 7, 4 Pre: 8, 5

DATA STRUCTURES
UNIT III TREES

Figure (b)
Now the next last data in post-order list is 4, so the root node of the left-subtree of the node that
contains a value 2 is 4. The data before 4 in the in-order list from the left sub-tree of the node
contains a value 4, but as there is no data present before 4 in the in-order list, the left sub-tree
of
the node with value 4 is empty. The data that comes to the right of 4 in the in-order list forms
the right sub-tree of the node 4. The following figure shows the binary tree after expanding the
left and right subtree of the node that contains a value 4.

2
In: 6, 9, 3
4 Pre: 9, 6, 3
In: 8, 5
Post: 8,
5 Figure (c)
7

Since, we are now left with only one value 7 in both the post order and in-order form we simply
represent it with a node as shown in following figure.

In: 6, 9, 3
4 Post: 9, 6, 3
In: 8, 5
Post: 8,
7 5

Figure (d)
The above procedure is applied for each node and all the data are picked from the post-order list
and are placed. Their respective sub-tree is constructed as a result the whole sub-tree is
constructed. The following figure (e) to (i) shows the construction of nodes one by one.

DATA STRUCTURES
UNIT III TREES

1
1
2 In: 6, 9, 3
2 In: 6, 9, 3 Post: 9, 6,
Post: 9, 6, 4 5 3
4 3
5
7 8
7
In: 8
Post: 8

Figure (e) Figure (f)

1 1
1

2 3 2 3
2 3

4 5 4 5 6 4 5 6

8 7 8
7 In: 9 7 8 9
In: 6, 9 Post:
Post: 9, 6 9

Figure (g) Figure (h) Figure (i)

The figure (i) shows the binary tree, which is reconstructed from the given in-order and post-
order traversals.

4.8 Threaded Binary Trees: - The binary trees with n nodes, 2n pointers are required of
which (n+1) are NULL pointers. To utilize these empty pointers, a new concept called threads is
introduced.
Threads are also links or pointers but replace NULL pointer by pointing to some useful
information in a binary tree.

To utilize, i.e. to avoid, NULL pointers in a binary tree two types of threads are used lthread i.e.
left thread and rthread i.e. right thread.

DATA STRUCTURES
UNIT III TREES

1. If the node left child is NULL, then it is replaced with inorder predecessor of node during
inorder traversal of binary tree.
2. If the node right child is NULL, then it is replaced with inorder successor of node during
inorder traversal of binary tree.
Inorder to distinguish left child and inorder predecessor, left thread is used as follows:
• If the left thread is 1 then it is inorder predecessor of node.
• If the left thread is 0 then it is left child of node.
Inorder to distinguish rightchild and inorder successor, right thread is used as follows:
• If the right thread is 1 then it is inorder successor of node.
• If the right thread is 0 then it is right child of node.
Here both left and right NULL pointers are made to point to inorder predecessor and inorder
successor respectively. The predecessor threads are useful for reverse inorder traversal and
postorder traversal.
Linked List Representation of Threaded Binary Tree:-
struct TBT
{
struct TBT *lchild;
int lthread;
int element;
int rthread;
struct TBT*rchild;
};
The idea of threaded binary trees is to make inorder traversal faster and do it without stack and
without recursion. A binary tree is made threaded by making all right child pointers that would
normally be NULL point to the inorder successor of the node.
Consider the following example:-
A

B C

F D E
Fig: Binary Tree
G

DATA STRUCTURES
UNIT III TREES

Inorder traversal for the above Binary Tree is G, F, B, A, D, C, E.

The following is Threaded BT of above BT:

B C

F D E
NULL NULL
G

Fig: Threaded BT
The left child of node G and the right child of node E are NULL due to absence of an inorder
predecessor and inorder successor respectively.

B 0 A 0 C

Lchild Lthread Element Rthread Rchild

F 0 B 1 A C 1 E 1 \0

G 0 F 1 B A 1 D 1 C

\0 1 G 1 F D 0 C 0 E

The above example shows the thread binary trees during inorder traversal of binary tree:
1. If the lthread is 0 then it is leftchild of element
2. If the lthread is 1 then it is inorder predecessor of element
3. If the rthread is 0 then it is rightchild of element
4. If the rthread is 1 then it is inorder successor of element
Inserting a node into a Threaded Binary Tree: Insertion in Binary threaded tree is similar to
insertion in binary tree but we will have to adjust the threads after insertion of each element.
Let tmp be the newly inserted node. There can be three cases during insertion:
Case 1: Insertion in empty tree
Both left and right pointers of tmp will be set to NULL and new node becomes the root.
root = tmp;

DATA STRUCTURES
UNIT III TREES

tmp -> left = NULL;

tmp -> right = NULL;
Case 2: When new node inserted as the left child
After inserting the node at its proper place we have to make its left and right threads points to
inorder predecessor and successor respectively. The node which was inorder successor. So the
left and right threads of the new node will be-
tmp -> left = par ->left;
tmp -> right = par;
Before insertion, the left pointer of parent was a thread, but after insertion it will be a link
pointing to the new node.
par -> lthread = 0;
par -> left = temp;
Following example show a node being inserted as left child of its parent.

After insertion of 13,

DATA STRUCTURES
UNIT III TREES

Predecessor of 14 becomes the predecessor of 13, so left thread of 13 points to 10.

Successor of 13 is 14, so right thread of 13 points to left child which is 13.
Left pointer of 14 is not a thread now, it points to left child which is 13.

Case 3: When new node is inserted as the right child

The parent of tmp is its inorder predecessor. The node which was inorder successor of the parent
is now the inorder successor of this node tmp. So the left and right threads of the new node will
be-
tmp -> left = par;
tmp -> right = par -> right;
Before insertion, the right pointer of parent was a thread, but after insertion it will be a link
pointing to the new node.
par -> rthread = 0;
par -> right = tmp;
Following example shows a node being inserted as right chile=d of its parent.

DATA STRUCTURES
UNIT III TREES

After 15 inserted,

Successor of 14 becomes the successor of 15, so right thread of 15 points to 16

Predecessor of 15 is 14, so left thread of 15 points to 14.
Right pointer of 14 is not a thread now, it points to right child which is 15.

4.9 Binary Search Trees: - BST is created inorder to access the elements faster. BST is created
using the following procedure: When a number is compared with the contents of a root node in
a tree,
1. A left branch is taken if the number is smaller than the contents of root node.
2. A right branch is taken if greater (or) equal to the contents of root node.
If the input list is as follows: 20 17 16 8 10 7 18 13 Then the binary tree shown in following figure
will result:

6 1

5 8

1
7

DATA STRUCTURES
UNIT III TREES

Fig: BST
The binary tree of above type has the property that all the elements in the left-subtree of a root
node N are less than the content of N and all the elements in the right sub-tree of root node N
are greater than (or) equal to the contents of N.
A binary tree that has these properties is called a binary search tree. If a binary search tree is
traversed in in-order then the contents of each node are printed in ascending order.
4.9.1 Operations on a BST: -
1. Searching of a node in a BST: - To search any node in a binary tree, initially the data i.e. to be
searched is compared with the data of the root node.
o If the data is equal to the data of the root node then the searching is successful.
o If the data is found to be greater than the data of the root node then the searching process
proceeds in the right sub-tree of the root node.
Otherwise,
o Searching process proceeds in the left subtree of the root node.
The above procedure is repeated for the left (or) right sub-tree until the data is found. While
searching the data, if the leaf node of tree is reached and the data is not found then it is
concluded that the data is not present in the tree.
2. Insertion of a node in a BST: - To insert any node into a BST, initially the data i.e. to be inserted
is compared with the data of the root node. If the data is found to greater than (or) equal to the
data of the root node then the new node is inserted in the right sub-tree of the root node;
otherwise the new node is inserted in the left sub-tree of the root node.
Now the root node of the right (or) left sub-tree is taken and its data is compared with the data
that is to be inserted and the same procedure is repeated. This is done till the left (or) the right
sub-tree where the new node is to be inserted is found to be empty. Finally, the new node is
made as appropriate child of some node.
3. Deletion from a binary tree: - The following are four possible cases that we need to consider
1. The node containing the data has no children
2. The node containing the data has exactly one child
3. The node containing the data has two children

DATA STRUCTURES
UNIT III TREES

Before deleting the element in binary tree, we need to search for the element whether it is part
of binary tree (or) not

Case (1): In this case since the node to be deleted has no children, the memory used by this node
should be freed and either the left link (or) the right link of the parent node should be set to
NULL.
Case (2): In this case since the node to be deleted has one child we have to adjust the pointer of
the node to be deleted, such that after deletion the parent node must point to the child of the
node being deleted.
Case (3): In this case since the node to be deleted has two children the solution is tricky we need
to find the inorder successor of node to be deleted and the data of this in-order successor should
now be copied into the node to be deleted and a pointer is setup pointing to the in-order
successor. The inorder successor should then be deleted using the same procedure as for deleting
a one child (or) a zero child node. Thus, the whole logic of deleting a node with two children is to
locate the in-order successor, copy its data and reduce the problem to a simple deletion of a node
with one (or) zero child.
Example: -

2 2
0 0
2
3 2
1 1
7 7 3
1 2
6 8 5 6 1 2
8 5
5 5
2 2
8 4 8 2 2
9
4 9
9
1 1
0 0

Initial BST After Insertion of 7 [to 8 left]

Figure (i) Figure (ii)

DATA STRUCTURES
UNIT III TREES

2 2
0 0

1 2 1 2
7 3 7 3

6 1 2 6 1 2
8 5 8 5

5 8 2 2 5 8 2
2
4 9 4
9
1 9
0

After deletion of 7 [parent-.>right=NULL] After deletion of 10 [parent-.>right=cur->left]

Figure (iii) Figure (iv)

2 2
0 0

2 1 2
1
3 8 3
7

6 1 2 6 2
8 9 9

5 8 5 8
2
2
4
4
9 9

After deletion of 25 [since two child, find inorder After deletion of 17 [since two child, find inorder
successor [29] and replace 25 with 29. Delete inorder successor [18] and replace 17 with 18. Delete
successor [29]. Parent->right=NULL] Figure (v) inorder successor [18]. Parent->right=NULL Figure

2
(vi)

1 2

6 2

5 8

DATA STRUCTURES
UNIT III TREES

Figure (vii)
After deletion of 20 [since two child, find inorder successor[23] and replace 20 with 23. Delete

inorder successor [23]. Parent->right=cur->right.

4.10 Height balanced binary tree: A binary tree is balanced if for every node in the tree has
a balance factor of -1, 0 and 1. Each node in a binary tree has a balance factor, which is equal to
the height of the left subtree minus the height of the right subtree. A binary tree is balanced if
every balance factor is of 0, 1, (or) -1.

Height of a node is number of steps to leaf node from the node. The height of the tree is the
height of its root node.

2 2
3 3

2 9 2
9
4 4

1 6 1 2
6 2
8 8 9
9

5 8 5 8

Figure (i) Height balanced Binary Tree Figure (ii) Not a Height balanced Binary Tree

Need of Balanced Binary Tree: - Simple binary trees are not perfect. If we insert a data into
already ordered data into a simple binary tree, you get a degenerate tree. All the insertions go to
the right; all the left pointers are NULL. So, the complexity increases from O (logN) to O (N).
One solution to this problem is to use a balanced binary tree. This involves a little more work,
and a more complicated insertion algorithm. That is balanced tree.
Advantages of height balanced binary trees: -
1. Height balanced binary tree are balanced.
DATA STRUCTURES
UNIT III TREES

2. Operations that run in time proportional to the height of the tree are O (logN), N the
number of nodes with limited performance variance.

4.10.1 Types of the balanced binary trees: -

Some of the more common types are

1) AVL-trees
2) Red-black trees
3) 2-3 tree

AVL-Tree: - These were invented by Adleson-Velskii and Landis in 1962 (hence the name AVL)

Red-black tree: - These are standard binary trees that satisfy the following conditions:

1. Every node is either red or black.

2. Every external node (NULL) is black.
3. No red node can have a red parent.
4. Every simple path from a node to an external contains the same number of black nodes.

B-tree: - A B-tree of order m is a tree exhibiting the following properties

1. The root is either a leaf or has between 2 and m children.

2. All the non-leaf nodes (except the root) have between m/2 and m children.
3. All leafs are at the same depth.

B-Tree of order 3 is known as 2-3 trees.

B-tree of order 4 is known as 2-3-4 trees.

DATA STRUCTURES