Chapter 5

Tree and Graph

5.1. Tree Structure

A tree is a set of nodes and edges that connect pairs of nodes. It is an abstract model of a hierarchical
structure. Generally, a tree has the following structure:
 One node distinguished as root.
 Every node N except the root is connected from exactly to other node P. P is N's parent, and N is
one of P's children.
 There is a unique path from the root to each node.
 The number of edges in a path is the length of the path.

5.1.1. Tree Terminologies

Consider the following tree:
A

B E F G

C D H I J

K L M

Root node: a node without a parent. A

Internal node: a node with at least one child. A, B, F, I, J
External (leaf) node: a node without a child.  C, D, E, H, K, L, M, G
Ancestors of a node: parent, grandparent, great-grandparent, etc of a node.
Ancestors of K  A, F, I
Descendants of a node: children, grandchildren, great-grandchildren etc of a node.
Descendants of F  H, I, J, K, L, M
Depth of a node: number of ancestors or length of the path from the root to the node.
Depth of H 2
Height of a tree: depth of the deepest node.  3
Sub tree: a tree consisting of a node and its descendants.

H I J

K L M

Binary tree: a tree in which each node has at most two children called left child and right child.

Full binary tree: a binary tree where each node has either 0 or 2 children.

Balanced binary tree: a binary tree where each node except the leaf nodes has left and right children and all
the leaves are at the same level.

Complete binary tree: a binary tree in which the length from the root to 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.
Binary search tree (ordered binary tree): a binary tree that may be empty, but if it is not empty it satisfies
the following.
 Every node has a key and no two elements have the same key.
 The keys in the right sub-tree are larger than the keys in the root.
 The keys in the left sub-tree are smaller than the keys in the root.
 The left and the right sub-trees are also binary search trees.

10

6 15

4 8 14 18

7 12 16 19

11 13

5.1.2. Operations on Binary Search Tree

Consider the following definition of binary search tree.

struct Node
{
int Num;
Node * Left, *Right;
};
Node *RootNodePtr=NULL;
5.1.2.1. Insertion
When a node is inserted the definition of binary search tree should be preserved.
Suppose there is a binary search tree whose root node is pointed by RootNodePtr and we want to insert a
node (that stores 17) pointed by InsNodePtr.

Case 1: if there is no data in the tree (i.e. RootNodePtr is NULL)

- The node pointed by InsNodePtr should be made the root node.

InsNodePtr RootNodePtr RootNodePtr



17 17

Case 2: if there is data

- Search the appropriate position.
- Insert the node in that position.

RootNodePtr
InsNodePt RootNodePtr
r
InsertBST(RootNodePtr, InsNodePtr) 
17 10 10

6 15 6 15

4 8 14 4 8 14 18
18

7 12 7 12 16 19
16 19

11 13 11 13 17
 Implementation:

void InsertBST(Node *RNP, Node *INP)

{
//RNP=RootNodePtr and INP=InsNodePtr
int Inserted=0;
while(Inserted = =0)
{
if(RNP->Num > INP->Num)
{
if(RNP->Left = = NULL)
{
RNP->Left = INP;
Inserted=1;
}
else
RNP = RNP->Left;
}
else
{
if(RNP->Right = = NULL)
{
RNP->Right = INP;
Inserted=1;
}
else
RNP = RNP->Right;
}
}
}

5.1.2.2. Traversing
Binary search tree can be traversed in three ways.
a. Pre order traversal - traversing binary tree in the order of parent, left and right.
b. Inorder traversal - traversing binary tree in the order of left, parent and right.
c. Postorder traversal - traversing binary tree in the order of left, right and parent.
 Example:
RootNodePtr

10

6 15

4 8 14 18

7 12 16 19

11 13 17

Preorder traversal - 10, 6, 4, 8, 7, 15, 14, 12, 11, 13, 18, 16, 17, 19
Inorder traversal - 4, 6, 7, 8, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19
==> Used to display nodes in ascending order.
Postorder traversal- 4, 7, 8, 6, 11, 13, 12, 14, 17, 16, 19, 18, 15, 10

5.1.2.3 Application of binary tree traversal

- Store values on leaf nodes and operators on internal nodes

Preorder traversal: - used to generate mathematical expression in prefix notation.

Inorder traversal: - used to generate mathematical expression in infix notation.
Postorder traversal: - used to generate mathematical expression in postfix notation.

Example:

Preorder traversal - + – A * B C + D / E F  Prefix notation

– + Inorder traversal - A – B * C + D + E / F  Infix notation
Postorder traversal - A B C * – D E F / + +  Postfix notation
A * D /

B C E F
 Inorder(CurrNodePtr->Left);
cout<< CurrNodePtr->Num;
Implementation: // or any operation on the node
Inorder(CurrNodePtr->Right);
void Preorder (Node *CurrNodePtr) }
{ }
if(CurrNodePtr ! = NULL)
{ void Postorder (Node *CurrNodePtr)
cout<< CurrNodePtr->Num; {
// or any operation on the node if(CurrNodePtr ! = NULL)
Preorder(CurrNodePtr->Left); {
Preorder(CurrNodePtr->Right); Postorder(CurrNodePtr->Left);
} Postorder(CurrNodePtr->Right);
} cout<< CurrNodePtr->Num;
void Inorder (Node *CurrNodePtr) // or any operation on the node
{ }
if(CurrNodePtr ! = NULL) }
{

5.1.2.4. Searching

To search a node (whose Num value is Number) in a binary search tree (whose root node is pointed by
RootNodePtr), one of the three traversal methods can be used.

Function call:
ElementExists = SearchBST (RootNodePtr, Number);
// ElementExists is a Boolean variable defined as: bool ElementExists = false;

Implementation:
bool SearchBST (Node *RNP, int x)
{
if(RNP = = NULL)
return(false);
else if(RNP->Num = = x)
return(true);
else if(RNP->Num > x)
return(SearchBST(RNP->Left, x));
else
return(SearchBST(RNP->Right, x));
}
 When we search an element in a binary search tree, sometimes it may be necessary for the SearchBST
function to return a pointer that points to the node containing the element searched. Accordingly, the
function has to be modified as follows.

Function call:
SearchedNodePtr = SearchBST (RootNodePtr, Number);
// SearchedNodePtr is a pointer variable defined as: Node *SearchedNodePtr=NULL;

Implementation:
Node *SearchBST (Node *RNP, int x)
{
if((RNP = = NULL) || (RNP->Num = = x))
return(RNP);
else if(RNP->Num > x)
return(SearchBST(RNP->Left, x));
else
return(SearchBST (RNP->Right, x));
}

5.1.2.5. Deletion

To delete a node (whose Num value is N) from binary search tree (whose root node is pointed by
RootNodePtr), four cases should be considered. When a node is deleted the definition of binary search tree
should be preserved.

Consider the following binary search tree.

rot

10

6 14

3 8 12 18

4 7 9 11 13 16 19
2

15 17
1 5
 Case 1: Deleting a leaf node (a node having no child), e.g. 7
RootNodePtr
RootNodePtr

Delete 7 
10
10

6 14
6 14

3 8 12 18
3 8 12 18

4 9 11 13 16 19
16 2
2 4 7 9 11 13 19

15 17
17 1 5
5 15
1

Case 2: Deleting a node having only one child, e.g. 2

To delete a node with only one child, one of the following is done

 If the deleted node is the left child of its parent and the deleted node has only the left child, the left child
of the deleted node is made the left child of the parent of the deleted node.
 If the deleted node is the left child of its parent and the deleted node has only the right child, the right
child of the deleted node is made the left child of the parent of the deleted node.
 If the deleted node is the right child of its parent and the node to be deleted has only the left child, the left
child of the deleted node is made the right child of the parent of the deleted node.
 If the deleted node is the right child of its parent and the deleted node has only the right child, the right
child of the deleted node is made the right child of the parent of the deleted node.
RootNodePtr
RootNodePtr

Delete 2 
10
10

6 14
6 14

3 8 12 18
3 8 12 18

4 9 11 13 16 19
16 1
2 4 7 9 11 13 19

15 17
17 5
5 15
1
 Case 3: Deleting a node having two children, e.g. 6

To delete a node with two children one of the following is done

 If the deleted node is the left child of its parent, one of the following is done
o The left child of the deleted node is made the left child of the parent of the deleted node, and
o The right child of the deleted node is made the right child of the node containing largest element in
the left of the deleted node
OR
o The right child of the deleted node is made the left child of the parent of the deleted node, and
o The left child of the deleted node is made the left child of the node containing smallest element in the
right of the deleted node

 If the deleted node is the right child of its parent, one of the following is done
o The left child of the deleted node is made the right child of the parent of the deleted node, and
o The right child of the deleted node is made the right child of the node containing largest element in
the left of the deleted node
OR
o The right child of the deleted node is made the right child of the parent of the deleted node, and
o The left child of the deleted node is made the left child of the node containing smallest element in the
right of the deleted node

RootNodePtr RootNodePtr

Delete 6 
10 10

6 14 8 14

3 8 12 18 7 9 12 18

4 7 9 11 13 16 19 11 13 16 19
2 3

15 17 15 17
1 5 4
2

1 5
 RootNodePtr
RootNodePtr

Delete 6  10
10
3 14
6 14

2 4 12 18
3 8 12 18
5 11 13 16 19
1
4 7 9 11 13 16 19
2
8 15 17
15 17
1 5
7 9

Approach 2: Deletion by copying- the following is done

 Copy the node containing the largest element in the left (or the smallest element in the right) to the node
containing the element to be deleted
 Delete the copied node.

RootNodePtr RootNodePtr

Delete 6 
10 10

6 14 5 14

3 8 12 18 3 8 12 18

2 4 7 9 11 13 16 19 2 4 7 9 11 13 16 19

15 17 15 17
1 5 1

RootNodePtr RootNodePtr

10 10
Delete 6 
6 14 14
7

3 8 12 18 12
3 8 18

4 7 9 11 13 16 19 16
2 2 4 9 11 13 19

15 17 5 17
1 5 15
1
 Case 4: Deleting the root node, 10
Approach 1: Deletion by merging- one of the following is done

 If the tree has only one node the root node pointer is made to point to nothing (NULL)
 If the root node has left child
o the root node pointer is made to point to the left child
o the right child of the root node is made the right child of the node containing the largest element in
the left of the root node
 If root node has right child
o the root node pointer is made to point to the right child
o the left child of the root node is made the left child of the node containing the smallest element in the
right of the root node

RootNodePtr RootNodePtr

RootNodePtr
10 Delete 10  6

6 14 3 8

3 8 12 18 4 7 9
2

4 7 9 11 13 16 19
2 1 5 14

15 17 12
1 5 18

11 13 16 19

15 17
 RootNodePtr RootNodePtr

RootNodePtr

10 14
Delete 10 
6 14 12 18

3 8 12 18 16
11 13 19

4 7 9 11 13 16 19 17
2 6 15

15 17 8
1 5 3

2 4 7 9

1 5
Approach 2: Deletion by copying: -
 Copy the node containing the largest element in the left (or the smallest element in the right) to the node
containing the element to be deleted
 Delete the copied node

RootNodePtr
RootNodePtr

9
10 Delete 10 

6 14
6 14

3 8 12 18
3 8 12 18

4 7 11 13 16 19
16 2
2 4 7 9 11 13 19

15 17
17 1 5
5 15
1
 RootNodePtr
RootNodePtr

11
10 Delete 10 

6 14
6 14

3 8 12 18
3 8 12 18

4 7 9 16 19
16 2 13
2 4 7 9 11 13 19

15 17
17 1 5
5 15
1

5.2. Graphs

5.2.1. Definitions

 A generalisation of the tree, a graph, is a data structure in which any node can link to any
other node.
 A simple graph G=(V, E) consists of a nonempty set of vertices V and a (possibly empty)
set of edges E. Figure 1a-c shows examples of simple graphs.
 Note that there must be at least one vertex be there need not be any edges, as in Figure 1a.
 Also note that a graph may consist of two unconnected sets of nodes, as in Figure 1b.
 A complete graph is one in which every node is connected to every other node (Figure 1d).
 A multi-graph is a graph in which two nodes can be joined by multiple edges (Figure 1e).
 A pseudo graph is a graph in which loops can occur, i.e. a node can be joined to itself
(Figure 1f).
 A directed graph, or digraph, is one in which the edges have a direction. Finally, a weighted
graph is one in which each edge has an associated value, or weight.
 Figure 1 – Examples of graphs: (a-c) simple graphs; (d) a complete graph; (e) a multigraph;
(f) a pseudograph; (g) a digraph; (h) a weighted graph

5.2.2. Graph Traversal Algorithm

Traversing the graph means examining all the nodes and vertices of the graph. There are two standard
methods to traverse in graphs. Let’s discuss each one of them in detail.

o Breadth First Search

o Depth First Search

Breadth First Search (BFS) Algorithm

Breadth first search is a graph traversal algorithm that starts traversing the graph from root node and explores
all the neighboring nodes. Then, it selects the nearest node and explore all the unexplored nodes. The
algorithm follows the same process for each of the nearest node until it finds the goal.

The algorithm of breadth first search is given below. The algorithm starts with examining the node A and all
of its neighbors. In the next step, the neighbors of the nearest node of A are explored and process continues
in the further steps. The algorithm explores all neighbors of all the nodes and ensures that each node is
visited exactly once and no node is visited twice.
Algorithm
o Step 1: SET STATUS = 1 (ready state)
for each node in G
 o Step 2: Enqueue the starting node A
and set its STATUS = 2
(waiting state)
o Step 3: Repeat Steps 4 and 5 until
QUEUE is empty
o Step 4: Dequeue a node N. Process it
and set its STATUS = 3
(processed state).
o Step 5: Enqueue all the neighbors of
N that are in the ready state
(whose STATUS = 1) and set
their STATUS = 2
(waiting state)
[END OF LOOP]
o Step 6: EXIT

Example

Consider the graph G shown in the following image, calculate the minimum path p from node A to node E.
Given that each edge has a length of 1.

Solution:
Minimum Path P can be found by applying breadth first search algorithm that will begin at node A and will
end at E. The algorithm uses two queues, namely QUEUE1 and QUEUE2. QUEUE1 holds all the nodes
that are to be processed while QUEUE2 holds all the nodes that are processed and deleted from QUEUE1.
Lets start examining the graph from Node A.
1. Add A to QUEUE1 and NULL to QUEUE2.
QUEUE1 = {A}
QUEUE2 = {NULL}
2. Delete the Node A from QUEUE1 and insert all its neighbors. Insert Node A into QUEUE2
QUEUE1 = {B, D}
QUEUE2 = {A}
3. Delete the node B from QUEUE1 and insert all its neighbors. Insert node B into QUEUE2.
QUEUE1 = {D, C, F}
QUEUE2 = {A, B}
4. Delete the node D from QUEUE1 and insert all its neighbors. Since F is the only neighbor of it which has
been inserted, we will not insert it again. Insert node D into QUEUE2.
QUEUE1 = {C, F}
QUEUE2 = { A, B, D}
5. Delete the node C from QUEUE1 and insert all its neighbors. Add node C to QUEUE2.
QUEUE1 = {F, E, G}
QUEUE2 = {A, B, D, C}
6. Remove F from QUEUE1 and add all its neighbors. Since all of its neighbors has already been added, we
will not add them again. Add node F to QUEUE2.
QUEUE1 = {E, G}
QUEUE2 = {A, B, D, C, F}
7. Remove E from QUEUE1, all of E's neighbors has already been added to QUEUE1 therefore we will not
add them again. All the nodes are visited and the target node i.e. E is encountered into QUEUE2.
QUEUE1 = {G}
0QUEUE2 = {A, B, D, C, F, E}
Now, backtrack from E to A, using the nodes available in QUEUE2.
The minimum path will be A → B → C → E.

Depth First Search (DFS) Algorithm

Depth first search (DFS) algorithm starts with the initial node of the graph G, and then goes to deeper and
deeper until we find the goal node or the node which has no children. The algorithm, then backtracks from
the dead end towards the most recent node that is yet to be completely unexplored.

The data structure which is being used in DFS is stack. The process is similar to BFS algorithm. In DFS, the
edges that leads to an unvisited node are called discovery edges while the edges that leads to an already
visited node are called block edges.
Algorithm
o Step 1: SET STATUS = 1 (ready state) for each node in G
o Step 2: Push the starting node A on the stack and set its STATUS = 2 (waiting state)
o Step 3: Repeat Steps 4 and 5 until STACK is empty
o Step 4: Pop the top node N. Process it and set its STATUS = 3 (processed state)
o Step 5: Push on the stack all the neighbors of N that are in the ready state (whose STATUS = 1) and
set their
STATUS = 2 (waiting state)
[END OF LOOP]
o Step 6: EXIT

Example :

Consider the graph G along with its adjacency list, given in the figure below. Calculate the order to print all
the nodes of the graph starting from node H, by using depth first search (DFS) algorithm.
Solution:
Push H onto the stack
STACK : H
POP the top element of the stack i.e. H, print it and push all the neighbors of H onto the stack that are is
ready state.
Print H
STACK : A
Pop the top element of the stack i.e. A, print it and push all the neighbors of A onto the stack that are in ready
state.
Print A
Stack : B, D
Pop the top element of the stack i.e. D, print it and push all the neighbors of D onto the stack that are in ready
state.
Print D
Stack : B, F
Pop the top element of the stack i.e. F, print it and push all the neighbors of F onto the stack that are in ready
state.
Print F
Stack : B
Pop the top of the stack i.e. B and push all the neighbors
Print B
Stack : C
Pop the top of the stack i.e. C and push all the neighbors.
Print C
Stack : E, G
Pop the top of the stack i.e. G and push all its neighbors.
Print G
Stack : E
Pop the top of the stack i.e. E and push all its neighbors.
Print E
Stack :
Hence, the stack now becomes empty and all the nodes of the graph have been traversed.
The printing sequence of the graph will be :
H→A→D→F→B→C→G→E