UNIT II

HIERARCHICAL -

Trees: Preliminaries – Implementation of Trees – Tree

Traversals with an Application –
Binary Trees: Implementation – Expression Trees – Search Tree
ADT – Binary Search Trees–Red Black trees- Applications of
Trees

1
 Module 2
INTRODUCTION TO ADT:

Basic Terminology, Binary Trees and their

representation • Trees: Basic Terminology, Binary Trees and
Complete Binary Trees their representation, Complete Binary Trees,
Binary Search Trees, Threaded Binary Trees,
Operations on Binary Trees (Insertion, Deletion, Operations on Binary Trees (Insertion,
Search & Traversal). Deletion, Search & Traversal).
Binary Search Trees • Applications: Expression Evaluation,
Threaded Binary Trees • Case Study: Game Tree

Applications: Expression Evaluation,

Case Study: Game Tree

2
Coding competition
[Link]
[Link]
[Link]
[Link]

3
Trees

4
Introduction to Tree terminology

• A tree is an abstract model of a hierarchical structure that consists of nodes with a parent-child
relationship.
• for example, records, family trees and table of contents.

A tree is a finite set of one or more nodes such that:

(1) There is a specially designated node called the root.
(2) The remaining nodes are partitioned into n >= 0 disjoint sets T1, • • • Tn, where
each of these sets is a tree.
 T1, • • • Tn are called the subtrees of the root. 5
Introduction to Tree terminology
Node / Vertex
A Root

B C
Left subtree
Right subtree
D E F G

Edges H I Leaves

J K L M N

6
 What is a Tree?
Tree is a non-linear data structure which organizes data in a hierarchical structure

• Tree is a sequence of nodes

• There is a starting node known as a root node

• Every node other than the root has a parent node.
• Nodes may have any number of children

7
What is a Tree?
• A tree is a connected graph without any circuits.
• If in a graph, there is one and only one path between every pair of vertices, then
graph is called as a tree.

8
What is a Tree?

9
Tree-Basic Terminology
1) Root − Node at the top of the tree is called root.

• Every tree must have a root node.

10
Tree-Basic Terminology
2) Edge − In a tree data structure, the connecting
link between any two nodes is called as EDGE.

• In a tree with 'N' number of nodes there will be

a maximum of 'N-1' number of edges.

11
Tree-Basic Terminology

3) Parent − In a tree data structure, the node which is a

predecessor of any node is called as PARENT NODE.

• The node which has a branch from it to any other node

is called a parent node.

• Parent node can also be defined as "The node which

has child / children".

12
Tree-Basic Terminology

4) Child − the node which is descendant of any node is

called as CHILD Node.

• The node which has a link from its parent node is called
as child node.
• In a tree, any parent node can have any number of child
nodes.
• In a tree, all the nodes except root are child nodes.

13
Tree-Basic Terminology
5) Sibling − nodes which belong to same Parent are called as SIBLINGS.

• The nodes with the same parent are called Sibling nodes.

14
Tree-Basic Terminology

6) Leaf − the node which does not have a child is

called as LEAF Node.

• A leaf is a node with no child.

• The leaf nodes are also called as External Nodes.
• In a tree, leaf node is also called as 'Terminal' node.

15
 Tree-Basic Terminology
7) Internal nodes − the node which has atleast one
child is called as INTERNAL Node.

• Internal nodes are also called as 'Non-Terminal'

nodes.

16
 Tree-Basic Terminology
8) Degree− the total number of children of a node is
called as DEGREE of that Node.

• Degree of a node is total number of children it has.

• The highest degree of a node among all the nodes in a
tree is called as 'Degree of Tree'

17
 Tree-Basic Terminology
9) Level−
• in a tree each step from top to bottom is called
as a Level and
• the Level count starts with '0' and incremented
by one at each level (Step).

 The root node is said to be at Level 0 and

 the children of root node are at Level 1 and
 the children of the nodes which are at Level 1 will be
at Level 2 and so on...

18
 Tree-Basic Terminology
10) Height −
• The total number of edges from leaf node to a particular
node in the longest path is called as HEIGHT of that
Node.

• Height of the root node is said to be height of the tree.

• Height of all leaf nodes is '0'.

19
 Tree-Basic Terminology
11) Depth − the total number of egdes from root node
to a particular node is called as DEPTH of that Node.

 The total number of edges from the root node to a

leaf node in the longest path is said to be the Depth
of the tree.
 The highest depth of any leaf node in a tree is said to
be depth of that tree.
 In a tree, depth of the root node is '0'.

20
 Tree-Basic Terminology
12) Path −
• the sequence of Nodes and Edges from one node to
another node is called as PATH between that two
Nodes.

• Length of a Path is total number of nodes in that path.

• The path A - B - E - J has length 4.

21
 Tree-Basic Terminology
13) Subtree − each child from a node forms a
subtree recursively.

• Every child node will form a subtree on its

parent node.

14) Forest: It is a collection of disjoint trees.

From a given tree if we remove its root then we
get a forest.

22
Tree-Basic Terminology

Root Node: A
Parent of C and D: A
D is sibling of : B and C
Leaf Nodes: E, F, G, D
Internal Nodes: ABC
Depth of F: 2
Depth of Tree: 2
Depth of Root Node: 0
Height of Tree: 2
Height of A: 2
Height of G: 0
Degree of Node A: 3
Degree of Tree: 3
Degree of C 1

23
Characteristics of Trees
• Non-linear data structure
• Combines advantages of an ordered array
• Searching as fast as in an ordered array
• Insertion and deletion as fast as in the linked list

Application of Trees
• Directory structure of a file store
• Structure of arithmetic expressions
• Used in almost every 3D video game to determine what objects need to
be rendered.
• Used in almost every high-bandwidth router for storing router-tables.
• used in compression algorithms, such as those used by the .jpeg and .mp3
file- formats.
24
Representation Of Trees
Left Child-Right Sibling Representation

I Left child-right sibling node structure

List Representation

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

25
Representation Of Trees
Left Child-Right Sibling Representation

Left child-right sibling node structure

I
A
*B NULL

B C D

*E *C *G *D *H NULL
List Representation

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

NULL NULL *M *I NULL *J NULL NULL
*K *F NULL NULL

K L M
26
NULL *L NULL NULL NULL NULL
Implementation of Trees int main()
{ // Create root
create a simple tree with 4 nodes struct node* root = newNode(1);
/* following is the tree after above statement
#include <stdio.h> 1
#include <stdlib.h> /\
NULL NULL
struct node { */
int data; root->left = newNode(2);
struct node* left; root->right = newNode(3);
struct node* right;
}; /* 2 and 3 become left and right children of 1
1
// newNode() allocates a new node with the given data and NULL left and right /\
pointers // 23
/\/\
struct node* newNode(int data) NULL NULL NULL NULL
{ */
// Allocate memory for new node root->left->left = newNode(4);
struct node* node
= (struct node*)malloc(sizeof(struct node)); /* 4 becomes left child of 2
1
// Assign data to this node /\
node->data = data; 23
/\/\
// Initialize left and right children as NULL 4 NULL NULL NULL
node->left = NULL; /\
node->right = NULL; NULL NULL
return (node); */
} getchar(); 27
return 0; }
Basic Operation Of Tree Data Structure:

• Create – create a tree in the data structure.

• Insert − Inserts data in a tree.
• Search − Searches specific data in a tree to check whether it is present or not.
• Traversal:
- Preorder Traversal – perform Traveling a tree in a pre-order manner in the data
structure.
- In order Traversal – perform Traveling a tree in an in-order manner.
- Post-order Traversal –perform Traveling a tree in a post-order manner.

28
Tree Traversal -
Traversal is a process to visit all the nodes of a tree and may print their values too. Because, all nodes are connected via edges
(links) we always start from the root (head) node.
That is, we cannot randomly access a node in a tree.
1. Pre order tree traversal
2. In order tree traversal
3. Post order tree traversal

29
30
In-order Traversal
• In this traversal method, the left subtree is visited first, then the root and later the right
sub-tree. We should always remember that every node may represent a subtree itself.
• If a binary tree is traversed in-order, the output will produce sorted key values in an
ascending order.

We start from A, and following in-order traversal, we move to its left subtree B.B is also
traversed in-order. The process goes on until all the nodes are visited.
The output of in-order traversal of this tree will be − D → B → E → A → F → C → G

void inorder_traversal(struct node* root)

{
Algorithm –
if(root != NULL) {
Until all nodes are traversed − inorder_traversal(root->leftChild);
printf("%d ",root->data);
Step 1 − Recursively traverse left subtree. inorder_traversal(root->rightChild);
Step 2 − Visit root node.
}
Step 3 − Recursively traverse right subtree.

31
Pre-order Traversal - In this traversal method, the root node is visited first,
then
the left subtree and finally the right subtree.

Algorithm –

Step 1 − Visit root node.

Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.
void pre_order_traversal(struct node* root)
{
if(root != NULL) {
printf("%d ",root->data);
pre_order_traversal(root->leftChild);
pre_order_traversal(root->rightChild);
}
}

32
Post-order Traversal -
• In this traversal method, the root node is visited last, hence the name. First we
traverse the left subtree, then the right subtree and finally the root node.

Algorithm –

Until all nodes are traversed −

Step 1 − Recursively traverse left subtree.

Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

void post_order_traversal(struct node* root)

{
if(root != NULL) {
post_order_traversal(root->leftChild);
post_order_traversal(root->rightChild);
printf("%d ", root->data);
}
}
33
Introduction to Binary Trees
• Binary tree is a special tree data structure in which each node can have at most 2
children.
• Each node has either 0 child or 1 child or 2 children.

34
Binary Trees
• A binary tree, T, is either empty or such that
i. T has a special node called the root node
ii. T has two sets of nodes LT and RT, called the left subtree and right subtree
of T, respectively.
iii. LT and RT are binary trees.

35
Binary Trees

(a) Skewed and (b) complete binary trees

36
Representation of Binary Trees
1) Array Representation

2) Linked Representation

38
Binary Tree – Linked List Representation
• Use a linked list to represent a binary tree.
• Every node consists of three fields.
• left child address,
• actual data
• right child address. struct node
• Advantages: {
int data;
• No wastage of space struct node *left;
• Insertions and deletions are easier struct node *right;
• Disadvantages: };
• Does not provide direct access
• Needs additional space for storing left and right subtrees

39
Binary Tree – Linked List Representation

40
Binary Tree – Linked List Representation

41
Binary Tree – Linked List Representation
#include <stdio.h> // Create a new Node
#include <stdlib.h> struct node* createNode(value)
{
struct node { struct node* newNode = malloc(sizeof(struct
int item; node));
struct node* left; newNode->item = value;
struct node* right; newNode->left = NULL;
}; newNode->right = NULL;
int main() {
return newNode;
struct node* root =
}
createNode(1); // Insert on the left of the node
insertLeft(root, 12); struct node* insertLeft(struct node* root, int
insertRight(root, 9); value)
{
insertLeft(root->left, 5); root->left = createNode(value);
insertRight(root->left, 6); return root->left;
1 }

12 9 // Insert on the right of the node

struct node* insertRight(struct node* root, int
value) {
5 6 root->right = createNode(value);
return root->right; 42
Binary Tree Traversals
• Displaying (or) visiting order of nodes in a binary tree is called as Binary Tree Traversal.
• There are three types of binary tree traversals.
In - Order Traversal

Pre - Order Traversal

Post - Order Traversal

43
1. In-order Traversal (follows LDR)
 The left subtree is visited first, then the root, and later the right subtree.

void inorderTraversal(struct node* root)

{
if (root == NULL)
return;
// Visit Left subtree
inorderTraversal(root->left);
// Print the data
printf("%d ->", root->item);
// Visit right subtree
inorderTraversal(root->right);
}
44
2. Pre-order Traversal (follows DLR)
• The root node is visited first, then the left subtree and finally the right subtree.

void preorderTraversal(struct node* root)

{
if (root == NULL)
return;
// Print the data
printf("%d ->", root->item);
// Visit Left subtree
preorderTraversal(root->left);
// Visit right subtree
preorderTraversal(root->right);
}
45
3. Post-order Traversal (follows LRD)
• The left subtree is visited first, then the right subtree and finally the root node.

void postorderTraversal(struct node* root)

{
if (root == NULL)
return;
// Visit Left subtree
postorderTraversal(root->left);
// Visit right subtree
postorderTraversal(root->right);
// Print the data
printf("%d ->", root->item);
}
46
Implementation of Binary Tree using linked list -
// preorderTraversal traversal
void preorderTraversal(struct node* root)
#include <stdio.h>
{
#include <stdlib.h>
if (root == NULL) return;
// Print the data
struct node {
printf("%d ->", root->item);
int item;
// Visit Left subtree
struct node* left;
preorderTraversal(root->left);
struct node* right;
// Visit right subtree
};
preorderTraversal(root->right);
}
// Inorder traversal
// postorderTraversal traversal
void inorderTraversal(struct node* root)
void postorderTraversal(struct node* root)
{
{
if (root == NULL) return;
if (root == NULL) return;
// Visit Left subtree
// Visit Left subtree
inorderTraversal(root->left);
postorderTraversal(root->left);
// Print the data
// Visit right subtree
printf("%d ->", root->item);
postorderTraversal(root->right);
// Visit right subtree
// Print the data
inorderTraversal(root->right);
printf("%d ->", root->item);
}
} 47
 int main() {
// Create a new Node struct node* root = createNode(1);
struct node* createNode(value) { insertLeft(root, 12);
struct node* newNode = malloc(sizeof(struct node)); insertRight(root, 9);
newNode->item = value;
newNode->left = NULL; insertLeft(root->left, 5);
newNode->right = NULL; insertRight(root->left, 6);

return newNode; printf("Inorder traversal \n");

} inorderTraversal(root);

// Insert on the left of the node printf("\n\nPreorder traversal \n");

struct node* insertLeft(struct node* root, int value) { preorderTraversal(root);
root->left = createNode(value);
return root->left; printf("\n\nPostorder traversal \n");
} postorderTraversal(root);
}
// Insert on the right of the node Inorder traversal
struct node* insertRight(struct node* root, int value) { 5 ->12 ->6 ->1 ->9 ->
root->right = createNode(value); Preorder traversal
return root->right; 1 ->12 ->5 ->6 ->9 ->
}
Postorder traversal
5 ->6 ->12 ->9 ->1 -> 48
Binary Tree Traversals

49
Binary Tree Traversals

50
Binary Tree Traversals
Inorder Traversal

Preorder Traversal

Postorder Traversal

Level order Traversal

51
Application - Evaluate a Binary Expression Tree
• A binary expression tree is a binary tree where operators are stored in the tree’s
internal nodes and the leaves contain constants.

52
Find the output

110
100

53
Rules

54
55
Binary Tree Traversals

56
57
Binary Search Tree (BST)
 Binary Search tree can be defined as a class of binary trees, in
which the nodes are arranged in a specific order. This is also
called ordered binary tree.

 It may be empty. If it is not empty, it satisfies the following

properties:
 Every element has a key, and no two elements have the
same key, that is, the keys are unique.
 In a BST, the value of all the nodes in the left sub-tree is less
than the value of the root.
 Similarly, the value of all the nodes in the right sub-tree is
greater than or equal to the value of the root.
 The left and right subtrees are also binary search trees. This
rule will be recursively applied to all the left and right sub-
trees of the root. 58
Advantages of using binary search tree
• Searching becomes very efficient in a binary search tree since, we get a hint at each
step, about which sub-tree contains the desired element.

• The binary search tree is considered as efficient data structure compared to arrays and
linked lists. In the searching process, it removes half sub-tree at every step.

• It also speeds up the insertion and deletion operations compared to that in array and
linked list.

Operations of BST
• Insertion
• Search
• Deletion
• Traversal
59
BST Insertion

• Insert values 43, 10, 79, 90, 12, 54, 11, 9, 50 into a BST

60
BST Insertion

61
BST Searching
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 -

• First, compare the element to be searched with the root element of the tree.
• If root is matched with the target element, then return the node's location.
• 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.
• If it is larger than the root element, then move to the right subtree.
• Repeat the above procedure recursively until the match is found.
• If the element is not found or not present in the tree, then return NULL.

64
BST Deletion

66
BST Deletion

67
BST Deletion

68
BST Deletion

69
To delete the given node from the binary search tree(BST), we
should follow the below rules –

[Link] Node –

70
Case 2 - If the node has 1 child, it is simply removed by swapping from the tree.

71
2

72
Program in C to Perform Operations on Binary Search Tree struct Node* search(struct Node* root, int value)
{
#include <stdio.h> if (root == NULL || root->data == value) {
#include <stdlib.h> return root;
}
if (value < root->data) {
struct Node { return search(root->left, value);
}
int data; return search(root->right, value);
struct Node* left; }
struct Node* right;
struct Node* delete(struct Node* root, int value)
}; {
if (root == NULL)
{
struct Node* createNode(int value) { return root;
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); }
newNode->data = value; if (value < root->data)
{
newNode->left = NULL; root->left = delete(root->left, value);
newNode->right = NULL; } else if (value > root->data)
{
return newNode; root->right = delete(root->right, value);
} } else
{
if (root->left == NULL) {
struct Node* insert(struct Node* root, int value) { struct Node* temp = root->right;
if (root == NULL) { free(root);
return temp;
return createNode(value); } else if (root->right == NULL) {
} struct Node* temp = root->left;
if (value < root->data) free(root);
return temp;
{ }
root->left = insert(root->left, value); struct Node* temp = root->right;
while (temp->left != NULL) {
} else if (value > root->data) { temp = temp->left;
root->right = insert(root->right, value); }
} root->data = temp->data;
root->right = delete(root->right, temp->data);
return root; }
} return root;
} 73
void inorderTraversal(struct Node* root)
{
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}

int main()
{
struct Node* root = NULL;
root = insert(root, 50);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 40);
root = insert(root, 70);
root = insert(root, 60);
root = insert(root, 80);

printf("Inorder traversal of the BST: ");

inorderTraversal(root);

struct Node* searchResult = search(root, 60);

if (searchResult != NULL) {
printf("Element found: %d", searchResult->data);
}
else
{
printf("Element not found.");
}

root = delete(root, 20);

root = delete(root, 30);
root = delete(root, 50);

printf("Inorder traversal after deletion of 20, 30, and 50: ");

inorderTraversal(root);

return 0;
} 74
Applications of Trees (Explain briefly below points)
Applications of tree data structure-
• Storing naturally hierarchical data - This includes a large amount of real-world data. Consider your computer's file system,
for example. The files and folders are organized hierarchically, with a root folder (typically designated by /) at the top. Each
subdirectory can have other subfolders, and so on. When storing such data, a tree data structure is the most intuitive
approach to do so
• Database indexing –
-Large collections of frequently updated records.
-A single key or a combination of keys is used to search.
-Use of key range queries for min/max searches
• Parsing - Parsing is the process of breaking down code into its constituent pieces using grammar.
• Artificial Intelligence – Used in the field of machine learning. They are used in various algorithms to model complex
relationships between inputs and outputs and to classify and make predictions. Decision Trees(used in AI &ML), Random
Forests,
• Cryptography - to provide integrity and authenticity guarantees for data transmitted over a network
• Binary Search – Searching
• Expression trees are beneficial for evaluating and manipulating mathematical expressions efficiently
• 3D video Game development 75
 AVL Tree
• The term AVL tree was introduced by Adelson-Velsky and Landis.
It is a balanced binary search tree and is the first data structure
like this. In the AVL tree, the heights of the subtree cannot be
more than one for all nodes.

It is clearly visible that the heights of the The heights of the left and right subtrees are
left and right subtrees are equal to, or less higher than 1.
than one.

76
Balance Factor in AVL Tree

• In the AVL tree, the term balance factor is very important.

• Balance Factor = height(left-subtree) – height(right – subtree)

• The balanced factor should be -1, 0 or +1. Otherwise, the tree will be considered an
unbalanced tree.

• To reduce the issue of time complexity in a binary search tree, the AVL tree was
introduced by Adelson-Velski & Landis. It is a self-balancing tree that helps in reducing
the complexity issue

The height of the left subtree is 3 and the

height of the right subtree is 2. That means
the balance factor is <=1 therefore the tree is
supposed to be balanced.

77
• Operations on AVL Tree

• The AVL tree is a balancing binary tree, and therefore it follows the same operations we perform in
the binary search tree.

1. Insertion

2. Deletion
• Insertion: The process of insertion is the same as it is executed in the binary search tree. However,
there are chances that it may point to a violation in the AVL tree property, and the tree may
require balancing. To balance a tree we can apply rotations.

• Deletion: The process of deletion is the same as it is executed in a binary search tree. It can affect
the balance factor of the tree, therefore, we need to utilize different types of rotations to balance
the tree.

78
AVL Rotation

• Left rotation
• Right rotation
• Left-Right rotation
• Right-Left rotation

79
[Link] Rotation: When we perform insertion at the left subtree, then
it is a left rotation.

80
2. Right Rotation: When we perform insertion at the right subtree,
then it is a right rotation.

81
82
3. Left-Right Rotation

83
• Right-Left Rotation

84
Expression trees
• An expression tree is a tree built up from the simple operands as the leaves of
binary tree and operators as the non -leaves of binary tree.
• It is a special kind of binary tree in which:-
(i) Each leaf node contains single operand.
(ii) Each non-leaf node contains a single binary operator.
(iii) The left and right subtrees of an operator node represent sub-expression that
must be evaluated before applying the operator at the root of the subtree.

85
• The levels in a binary expression tree represent the precedence of operators.
• The operators at the lower level must be evaluated first and then the operators at
the next level and so on and at the last operator at the root node is applied and
there by the expression is evaluated.

Prefix expression is - *-ab+cd similar to preorder traversal Postfix

expression is : - ab-cd+* similar to postorder traversal
86
Red-black tree

• The red-Black tree is a binary search tree.

• The prerequisite of the red-black tree is that we should know
about the binary search tree.
• In a binary search tree, the values of the nodes in the left subtree
should be less than the value of the root node, and the values of
the nodes in the right subtree should be greater than the value of
the root node.

87
• A Red-Black Tree is a self-balancing binary search tree where
each node has an additional attribute: a color, which can be
either red or black.
• The primary objective of these trees is to maintain balance
during insertions and deletions, ensuring efficient data retrieval
and manipulation..

88
Properties of Red-Black Trees

• A Red-Black Tree have the following properties:

[Link] Color: Each node is either red or black.

[Link] Property: The root of the tree is always black.

[Link] Property: Red nodes cannot have red children (no two
consecutive red nodes on any path).

[Link] Property: Every path from a node to its descendant null

nodes (leaves) has the same number of black nodes.

[Link] Property: All leaves (NIL nodes) are black.

89
90
91
Applications of Tree
• Hierarchical Structure: One reason to use trees might be
because you want to store information that naturally forms a
hierarchy.

• Searching Efficiency: Trees provide an efficient way to search

for data. It is faster than searching in a linear data structure like
an array or a linked list.

• Sorting: Trees can be used to sort data efficiently. For example,

in a self-balancing binary search tree, the data is automatically
sorted as it is inserted into the tree, making it easy to find the
minimum, maximum, and other values in the tree.
92
• Dynamic Data: Trees are dynamic data structures, which means
that they can grow and shrink as needed. This makes them well-
suited for applications where the data changes frequently, such as in
real-time systems.

• Efficient Insertion and Deletion: Trees provide efficient algorithms

for inserting and deleting data, which is important in many
applications where data needs to be added or removed frequently.

• Easy to Implement: Trees are relatively easy to implement,

especially when compared to other data structures like graphs. This
makes them a popular choice for many programming projects.

93