Chapter Five: Tree

and Graph

1
This Chapter Covers:
Tree:
 Basic concepts and definitions
 Binary tree
 Binary Search Tree (BST)
 Operations on BST: Insertion, Searching, Deletion,

2
 What is Tree?
The tree is a nonlinear hierarchical data structure and
comprises a collection of entities known as nodes. It connects
each node in the tree data structure using "edges”, both directed
and undirected.

A tree data structure is a hierarchical structure that is used to

represent and organize data in a way that is easy to navigate
and search.

The topmost node of the tree is called the root, and the nodes
below it are called the child nodes. Each node can have
multiple child nodes, and these child nodes can also have their
own child nodes, forming a recursive structure.
3
4
 Basic Terminologies In Tree DS
Root
In a tree data structure, the root is the
first node of the tree. The root node is
the initial node of the tree in data
structures.
In the tree data structure, there must
be only one root node.
Edge
In a tree in data structures, the
connecting link of any two nodes is
called the edge of the tree data
structure.
In the tree data structure, N number of
nodes connecting with N -1 number of
edges
5
 Basic Terminologies In Tree DS
Parent
In the tree in data structures, the node
that is the predecessor of any node is
known as a parent node, or a node with
a branch from itself to any other
successive node is called the parent
node
Child
The node, a descendant of any node, is
known as child nodes in data
structures.
In a tree, any number of parent nodes
can have any number of child nodes.
In a tree, every node except the root
node is a child node
6
 Basic Terminologies In Tree DS
Siblings
In trees in the data structure, nodes
that belong to the same parent are
called siblings
Leaf
Trees in the data structure, the node
with no child, is known as a leaf
node.
In trees, leaf nodes are also called
external nodes or terminal nodes.
Subtree
In the tree in data structures, each
child from a node shapes a sub-tree
recursively and every child in the
tree will form a sub-tree on its parent 7
node.
 Basic Terminologies In Tree DS
Internal nodes
Trees in the data structure have at
least one child node known as internal
nodes.
In trees, nodes other than leaf nodes
are internal nodes.
Sometimes root nodes are also called
internal nodes if the tree has more
than one node.
Degree
In the tree data structure, the total
number of children of a node is called
the degree of the node.
The highest degree of the node among
all the nodes in a tree is called the
Degree of Tree 8
 Basic Terminologies In Tree DS
Level
In tree data structures, the root node is
said to be at level 0, and the root node's
children are at level 1, and the children
of that node at level 1 will be level 2,
and so on.
Height
In a tree data structure, the number of
edges from the leaf node to the
particular node in the longest path is
known as the height of that node.
In the tree, the height of the root node
is called "Height of Tree".
The tree height of all leaf nodes is 0.

9
 Basic Terminologies In Tree DS
Depth
In a tree, many edges from the root node
to the particular node are called the depth
of the tree.
In the tree, the total number of edges from
the root node to the leaf node in the
longest path is known as "Depth of Tree".
In the tree data structures, the depth of
the root node is 0.
Path
In the tree in data structures, the sequence
of nodes and edges from one node to
another node is called the path between
those two nodes.
The length of a path is the total number of
nodes in a [Link]

10
 Representation of Tree structure
struct node

{
int data;

struct node *leftchild;

struct node *rightchild;

11
 Types of Trees
General Tree:
A tree in which there is no restriction on the number of children a node has, is
called a General tree. Examples are Family tree, Folder Structure.

Binary Tree:
In a Binary tree, every node can have at most 2 children, left and right
Binary trees are further divided into full binary tree and complete binary tree
based on its application.

12
Full Binary Tree:
If every node in a tree has either 0 or 2 children, then the tree is called a
full tree.

Complete Binary Tree:

is a binary tree in which the level of the any leaf node is either H or H-
1 where H is the height of the tree.
The deepest level should also be filled from left to right

13
 Types of Trees
Balanced Tree:
If the height of the left and right sub tree at any node differs at most
by 1, then the tree is called a balanced tree.

14
 Types of Trees
Binary Search Tree:
It is a binary tree with binary search property.
Binary search property states that the value or key of the left node is
less than its parent and value or key of right node is greater than its
parent. And this is true for all nodes

15
 Binary Search Tree
Binary Search Tree (BST) is a data structure that is commonly used to
implement efficient searching, insertion, and deletion operations.
Properties of BST is
 The left sub tree of a node will contain only nodes with keys lesser than the node’s key.
 The right sub tree of a node contains only nodes with keys greater than the node’s key.
 The left and right sub tree each, in turn, would be a binary tree.
 There must be no duplicate nodes in the tree.

16
 Operations in a Binary Search Tree
Searching in Binary Search Tree
Insertion in Binary Search Tree
Deletion in Binary Search Tree
Binary Search Tree (BST) Traversals
In order,
Pre order,
Post order

17
 Binary Search Tree
struct Node {
int key;
Node *left, *right;
};

Node* newNode(int key) {

Node* node = new Node();
node->key = key;
node->left = node->right = NULL;
return node;
}

18
 Searching in Binary Search Tree
To search for a key in the tree, we follow the step similar to a
binary search:

Steps:
Compare the key to be searched with the root’s key.
If the key is present at the root, then we have found the key.
If the key is lesser than the root’s value, we return the left subtree of the
node.
If the key is greater than the root’s value, we return the right subtree of
the node.
The search is continued recursively until the element is found, or all
nodes are exhausted.

19
 Searching in Binary Search Tree
Node* search(Node* root, int key) {
if (root == NULL || root->key == key)
return root; // Found or not found

if (key < root->key)

return search(root->left, key); // Go left

return search(root->right, key); // Go right

}

20
 Insertion in Binary Search Tree
To insert for a key in the tree, we follow the binary search
property and insert accordingly:

Steps:
Compare the key to be searched with the root’s key.
If the key is lesser than the root’s value, we return the left subtree of
the node.
If the key is greater than the root’s value, we return the right
subtree of the node.
This process is continued until we hit a leaf node. The new node is
inserted to this location as a new node.

21
 Insertion in Binary Search Tree
Node* insert(Node* root, int key) {
if (root == NULL)
return newNode(key);

if (key < root->key)

root->left = insert(root->left, key);
else
root->right = insert(root->right, key);

return root;
}

22
 Deletion in Binary Search Tree
Deletion in a binary search tree is more complex than
insertion.
It is mandatory to maintain the in-order sequence of the nodes
while deletion. There are three possible cases to consider:

1. Deleting a node with no children:

The node is simply removed from the tree. The in-order sequence is
already maintained in this case.

23
 Deletion in Binary Search Tree
2. Deleting a node with one child:
The node is removed and replaced with its child. In the implementation, we
copy the child node to the node to be deleted and then delete the child node.

3. Deleting a node with two children:

First, we find the in-order successor of the node. Then the contents of this in-
order successor are copied to the node to be deleted. Finally, the in-order
successor is deleted.

24
 Deletion in Binary Search Tree
struct node *deleteNode(struct node *root, int key) {
// Return if the tree is empty
if (root == NULL) return root;

// Find the node to be deleted

if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
// If the node is with only one child or no child
if (root->left == NULL) {
struct node *temp = root->right;
free(root);
return temp;
}
 Deletion in Binary Search Tree Cont.
else if (root->right == NULL) {
struct node *temp = root->left;
free(root);
return temp;
}

// If the node has two children

struct node *temp = minValueNode(root->right);

// Place the inorder successor in position of the node to be

deleted
root->key = temp->key;

// Delete the inorder successor

root->right = deleteNode(root->right, temp->key);
}
return root;
}
26
 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.
There are three ways which we use to traverse a tree −
In-order Traversal
Pre-order Traversal
Post-order Traversal

27
 In-order Traversal
The inorder traversal operation in a Binary Search Tree visits
all its nodes in the following order −
Firstly, we traverse the left child of the root node/current node, if any.
Next, traverse the current node.
Lastly, traverse the right child of the current node, if any.

Algorithm
1. START
2. Traverse the left subtree, recursively
3. Then, traverse the root node
4. Traverse the right subtree, recursively.
5. END

28
 In-order Traversal
void inorder(struct node *root) {
if (root != NULL) {
// Traverse left
inorder(root->left);

// Traverse root
cout << root->key << " -> ";

// Traverse right
inorder(root->right);
}
}

29
 Pre-order Traversal
The preorder traversal operation in a Binary Search Tree visits
all its nodes. However, the root node in it is first printed,
followed by its left subtree and then its right subtree.

Algorithm
1. START
2. Traverse the root node first.
3. Then traverse the left subtree, recursively
4. Later, traverse the right subtree, recursively.
5. END

30
 Pre-order Traversal
void preorder(struct node *root){
if (root != NULL) {
cout << root->key << " -> ";
preorder(root->left);
preorder(root->right);
}
}

31
 Post-order Traversal
postorder traversal also visits all the nodes in a Binary Search
Tree and displays them. However, the left subtree is printed
first, followed by the right subtree and lastly, the root node.

Algorithm
1. START
2. Traverse the left subtree, recursively
3. Traverse the right subtree, recursively.
4. Then, traverse the root node
5. END

32
 Post-order Traversal
void postorder(struct node *root){
if (root != NULL) {
postorder(root->left);
postorder(root->right);
cout << root->key << " -> ";

}
}

33
Traversal - Example

34
 Reading Assignment
Balancing a tree
Self-adjusting trees
Heaps
Polish notation and expression trees

35