Module-4 :

Trees
Trees
Root

leaf

5
 Introduction
● Definition (recursively): A tree is a finite set of one
or more nodes such that
– There is a specially designated node called root.
– The remaining nodes are partitioned into n>=0 disjoint set
T1,…,Tn, where each of these sets is a tree. T1,…,Tn are
called the subtrees of the root.
● Every node in the tree is the root of some subtree
 Height and Level
Level
node (13)
degree of a node 3 1 1
leaf (terminal)
nonterminal
parent 2 2 1 2 2 2 2
children
sibling
1 30 30 31 30 30 3 3
degree of a tree (3)
ancestor
level of a node 0 40 4 0 4 4
height of a tree (3)

12
Definitions
•Depth: The depth of a node is the number of edges from the root node to that specific node. For
example, the root node has a depth of 0, and its immediate children have a depth of 1 .
•Height: The height of a node is the number of edges on the longest path from that node to a leaf
node. A leaf node has a height of 0.

CHAPTER 5 13
● Example
A is the root node Property: (# edges) = (#nodes) - 1
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 level of E is 3 Level
The height (depth) of the tree is 4
The degree of node B is 2 A 1
The degree of the tree is 3
The ancestors of node I is A, C, H B C
The descendants of node C is F, G, H, I 2

H
3
D E F G
I
4
● Representation Of Trees
– List Representation
• we can write of Figure as a list in which each of the subtrees is also
a list
( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )
• The root comes first,
followed by a list of sub-trees
 Representation of Trees
● List Representation
– ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )
– The root comes first, followed by a list of sub-trees

data link 1 link 2 ... link n

needed in such a representation?
How many link fields are

17
● Representation Of
Trees (cont’d)
– Left Child- Right Sibling Representation
● Representation Of Trees (cont’d)
– Representation As A Degree Two Tree
Binary Trees
● Binary trees are characterized by the fact that any
node can have at most two branches
● Definition (recursive):
– A binary tree is a finite set of nodes that is either empty or
consists of a root and two disjoint binary trees called the
left subtree and the right subtree
● Thus the left subtree and the right subtree are
distinguished A A

B B
● Any tree can be transformed into binary tree
– by left child-right sibling representation
 Binary Trees
● The abstract data type of binary tree
 Binary Trees
● Two special kinds of binary trees:
(a) skewed tree, (b) complete binary tree
– The all leaf nodes of these trees are on two adjacent levels
Binary Trees
● Properties of binary trees
– Lemma 5.1 [Maximum number of nodes]:
1. The maximum number of nodes on level i of a binary tree
is 2i, i ≥0.
2. The maximum number of nodes in a binary tree of depth k
is 2k-1, k≥1.
– Lemma 5.2 [Relation between number of leaf nodes and
degree-2 nodes]:
For any nonempty 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.
● These lemmas allow us to define full and complete
binary trees
1) The maximum number of nodes at level ‘l’ of a binary tree is 2l.
Here level is the number of nodes on the path from the root to the node
(including root and node). Level of the root is 0.
This can be proved by induction.
For root, l = 0, number of nodes = 20 = 1
Assume that the maximum number of nodes on level ‘l’ is 2l
Since in Binary tree every node has at most 2 children, next level would
have twice nodes, i.e. 2 * 2l
•The maximum number of nodes in a tree of height of h = 2h+1-1
•The minimum of nodes in a tree of height of h= h+1
•If maximum nodes are given then what is the minimum height of the tree
•The minimum of nodes in a tree of height of h= h+1
•If minimum number of nodes is given then we can find the maximum
height of the tree n=h+1
=> h=n-1
 Relations between Number of
Leaf Nodes and Nodes of Degree 2
For any nonempty binary tree, T, if n0 is the
number of leaf nodes and n2 the number of nodes
of degree 2, then n0=n2+1
proof:
Let n and B denote the total number of nodes & branches in T.
Let n0, n1, n2 represent the nodes with no children, single child, and two children
respectively.
n= n0+n1+n2, ------------------------------------------------(1)
If a tree with n nodes then number of branches B = n-1
and can be written as B+1=n, -----------------------------------(2)
Therefore total number of branches in a tree are B=n1+2n2 ----------------------(3)

Substitute (3) in (2) 🡺n1+2n2+1= n ---------------------------------(4)

Substitute (1) in (4) 🡺n1+2n2+1= n0+n1+n2
🡺n0=n2+1

37
 Binary Trees
● Definition:
– A full binary tree of depth k is a binary tree of death k having
2k-1 nodes, k ≥ 0.
– A binary tree with n nodes and depth k is complete iff its
nodes correspond to the nodes numbered from 1 to n in the
full binary tree of depth k.
– From Lemma 5.1, the
height of a complete
binary tree with n nodes
is ⎡log2(n+1)-1⎤
 Binary Trees
● Binary tree representations (using array)
– Waste spaces: in the worst case, a skewed tree of depth k
requires 2k-1 spaces. Of these, only k spaces will be occupied
– Insertion or deletion
of nodes from the
middle of a tree
requires the
movement of
potentially many nodes
to reflect the change in
the level of these nodes
 Binary Trees
● Binary tree representations (using array)
– Lemma 5.3: If a complete binary tree with n nodes is
represented sequentially, then for any node with index i,
1 ≤ i ≤ n, we have
1. parent(i) is at ⎣i /2⎦ if i ≠ 1.
If i = 1, i is at the root and has no parent.
2. LeftChild(i) is at 2i if 2i ≤ n.
If 2i > n, then i has no left child.
3. RightChild(i) is at 2i+1 if 2i+1 ≤ n. A 1
If 2i +1 > n, then i has no left child
[1] [2] [3] [4] [5] [6] [7] B 2 C 3
A B C — D — E
Level 1 D E
Level 2 Level 3 4 5 6 7
 Binary Trees
● Binary tree representations (using link)
Binary Trees
● Binary tree representations (using link)
Binary Tree Traversals
● How to traverse a tree or visit each node in the tree
exactly once?
– There are six possible combinations of traversal
LVR, LRV, VLR, VRL, RVL, RLV
– Adopt convention that we traverse left before
right, only 3 traversals remain
LVR (inorder), LRV (postorder), VLR (preorder)

left_child data right_child

V
L: moving left : R: moving right
visiting
node
 Binary Tree Traversals
● Arithmetic Expression using binary tree
– inorder traversal (infix expression)
A/B*C*D+E
– preorder traversal (prefix expression)
+**/ABCDE
– postorder traversal
(postfix expression)
AB/C*D*E+
– level order traversal
+*E*D/CAB
 In-Order Traversal

Pre-Order Traversal Post-Order Traversal

47
#include<stdio.h>
#include<stdlib.h>
struct BTnode
{
int keyVal;
struct BTnode *leftNode;
struct BTnode *rightNode;
};
struct BTnode *getNode(int value)
{
struct BTnode *newNode = malloc(sizeof(struct BTnode));
newNode->keyVal = value;
newNode->leftNode = NULL;
newNode->rightNode = NULL;
return newNode;
}

struct BTnode *insert(struct BTnode *rootNode, int value)

{
if(rootNode == NULL)
return getNode(value);
if(rootNode->keyVal < value)
rootNode->rightNode = insert(rootNode->rightNode,value);
else if(rootNode->keyVal > value)
rootNode->leftNode = insert(rootNode->leftNode,value);
return rootNode;
}
void insertorder(struct BTnode *rootNode)
{
if(rootNode == NULL)
return;
insertorder(rootNode->leftNode);
printf("%d ",rootNode->keyVal);
insertorder(rootNode->rightNode);
}
int main()
{
struct BTnode *rootNode = NULL;
rootNode = insert(rootNode,7);
rootNode = insert(rootNode,4);
rootNode = insert(rootNode,8);
rootNode = insert(rootNode,1);
rootNode = insert(rootNode,5);
rootNode = insert(rootNode,2);
rootNode = insert(rootNode,9);
rootNode = insert(rootNode,3);
insertorder(rootNode);
return 0;
}
 Properties of Binary trees
Lemma1: Maximum number of nodes on level ‘i’ of a binary tree is 2i for i≥0

Lemma2: Total number of nodes in a full binary tree of level ‘i’ is 2i+1-1 for i≥0

Lemma3: Maximum number of nodes in binary tree of depth ‘k’ = 2k-1 for k ≥1

Lemma4: For any non-empty binary tree ‘T’ if n0 is the number of leaf nodes n2

is the number of degree2, then n0=n2+1 (Relation between number of leaf nodes

and degree-2 nodes)

52
Binary Tree Traversals
● Inorder traversal (LVR) (recursive version)
output: A / B * C * D + E

ptr
L
V
R
Binary Tree Traversals
● Preorder traversal (VLR) (recursive version)
output: + * * / A B C D E

V
L
R
 Binary Tree Traversals
● Postorder traversal (LRV) (recursive version)
output: A B / C * D * E +

L
R
V
CHAPTER 5 56
 Binary Tree Traversals
● Iterative inorder traversal
– we use a stack to simulate recursion
5 48 11
3 14
2 17
1
A B/ *C *D E+

L
V

output: A / B*C *D + E node

Trace Operations of Inorder Traversal

58
 Level Order Traversal
(using queue)

void level_order(tree_pointer ptr)

/* level order tree traversal */
{
int front = rear = 0;
tree_pointer queue[MAX_QUEUE_SIZE];
if (!ptr) return; /* empty queue */
addq(front, &rear, ptr);
for (;;) {
ptr = deleteq(&front, rear);

59
 if (ptr) {
printf(“%d”, ptr->data);
if (ptr->left_child)
addq(front, &rear,
ptr->left_child);
if (ptr->right_child)
addq(front, &rear,
ptr->right_child);
}
else break;
}
}

+*E*D/CAB

60
CHAPTER 5 61
CHAPTER 5 62
 Copying Binary Trees
tree_pointer copy(tree_pointer original)
{
tree_pointer temp;
if (original) {
temp=(tree_pointer) malloc(sizeof(node));
if (IS_FULL(temp)) {
fprintf(stderr, “the memory is full\n”);
exit(1);
}
temp->left_child=copy(original->left_child);
temp->right_child=copy(original->right_child);
temp->data=original->data;
return temp;
}
return NULL;
}
63
 Equality of Binary Trees
the same topology and data

int equal(tree_pointer first, tree_pointer second)

{
/* function returns FALSE if the binary trees first and
second are not equal, otherwise it returns TRUE */

return ((!first && !second) || (first && second &&

(first->data == second->data) &&
equal(first->left_child, second->left_child) &&
equal(first->right_child, second->right_child)))
}

64
CHAPTER 5 65
 Binary Search Tree
● Heap
– a min (max) element is deleted. O(log2n)
– deletion of an arbitrary element O(n)
– search for an arbitrary element O(n)
● Binary search tree
– Every element has a unique key.
– The keys in a nonempty left subtree (right
subtree) are smaller (larger) than the key in the
root of subtree.
– The left and right subtrees are also binary
search trees.
CHAPTER 5 66
Examples of Binary Search Trees

2 3 6
0 0 0

12 25 5 40 70

10 15 22 2 65 80

CHAPTER 5 67
 Searching a Binary Search Tree
tree_pointer search(tree_pointer root,int key)
{
/* return a pointer to the node that contains
key. If there is no such node, return NULL */

if (!root) return NULL;

if (key == root->data) return root;
if (key < root->data)
return search(root->left_child,key);
return search(root->right_child,key);
}

CHAPTER 5 68
 Another Searching Algorithm
tree_pointer search2(tree_pointer tree, int key)
{
while (tree) {
if (key == tree->data) return tree;
if (key < tree->data)
tree = tree->left_child;
else tree = tree->right_child;
}
return NULL;
}

CHAPTER 5 69
Insert Node in Binary Search Tree

3 3 3
0 0 0

5 40 5 40 5 40

2 2 80 2 35 80

Insert 80 Insert 35

CHAPTER 5 70
 Insertion into A Binary Search Tree
void insert_node(tree_pointer *node, int num)
{tree_pointer ptr,
temp = modified_search(*node, num);
if (temp || !(*node)) {
ptr = (tree_pointer) malloc(sizeof(node));
if (IS_FULL(ptr)) {
fprintf(stderr, “The memory is full\n”);
exit(1);
}
ptr->data = num;
ptr->left_child = ptr->right_child = NULL;
if (*node)
if (num<temp->data) temp->left_child=ptr;
else temp->right_child = ptr;
else *node = ptr;
}
} CHAPTER 5 71
 Insertion into BST and avoid
duplicate element

CHAPTER 5 72
CHAPTER 5 73
CHAPTER 5 74
1. Leaf node is the first node to be eliminated.

CHAPTER 5 75
CHAPTER 5 76
Deletion for A Binary Search Tree
1
3
leaf
0
node
5 80
T1 T2
1
2
2
T1 X

T2
CHAPTER 5 77
Deletion for A Binary Search Tree
non-leaf 4 4
node 0 0

20 60 20 55

10 30 50 70 10 30 50 70

45 55 45 52

52
Before deleting 60 After deleting 60

CHAPTER 5 78
2. The deleted node has just one child node.

CHAPTER 5 79
CHAPTER 5 80
3. There are two children of the to-be-deleted
node.

CHAPTER 5 81
CHAPTER 5 82
CHAPTER 5 83