Trees

Prepared by: Badhan Das

Definition
A connected acyclic graph is a tree.
Types of Trees
General Tree : a tree where each node can Binary Tree : is a specialized version of
have zero or many child nodes. There is no generalized tree. Here each node can have at
limitation on the degree of any node. most two nodes.
Important Terms
Path
Path refers to the sequence of nodes along the edges of a tree.

In this given tree,

1,2,4,8 is a path

But 1,2,4,5 is not since there is no

direct connection between 4 & 5.

Root
In a rooted tree, the node at the top of a tree is called the root. There is only
one root per tree and one path from the root node to any node.

Here, 1 is the root node of this tree.

From root node 1 to the node ‘10’

there is one path, 1,2,5,10 and no

other path exists between these two.

Parent
Any node accept the root node has an edge upward to a node called parent.
Only the root node does not have a parent.

The parent of node ‘5’ is ‘2’.

The parent of node ‘13’ is ‘6’.

Child
The node below a given node connected by its edge downward is called its
child node.

‘9’ is a child of ‘4’

‘11’ is a child of ‘5’

Leaf
The node which does not have any child is called leaf node.

In this example, ‘10’, ‘11’ are some of the

leaf nodes.
Subtree
Subtree represents the descendant of a node.

The subtree of the node ‘2’ includes

itself and the tree under that root.

Implementation of Binary Tree Data Structure
Remember class? You have studied in linked list.

Consider a single node first.

Link with its parent and children.

So, in a class of ‘Node’ to represent a node

1. Data
2. Parent pointer
3. Left_child pointer
4. Right_child pointer
Description
For example consider node ‘5’.

Class node

data := 5

*parent := ‘2’

*left_child := ‘10’

*right_child := ‘11’
Description [contd.]
For example consider a node ‘6’.

Class node

data := 6

*parent := ‘3’

*left_child := null

*right_child := ‘13’
Description [contd.]
For example consider a leaf node ‘14’.

Class node

data := 14

*parent := ‘7’

*left_child := null

*right_child := null
Description [contd.]
For example consider the root node ‘1’.

Class node

data := 1

*parent := null

*left_child := ‘2’

*right_child := ‘3’
Understandings
● In a binary tree, a node has at most 2 children. That means it can have 0,
1 or 2 children.
● If a node has 0 child, then it is a leaf node. A leaf node does not have a
left_child or a right_child. So these pointers will point to NULL.
● If a node has 1 child, then if it is left child, the left_child pointer will point
to that and the right_child will point to NULL. Otherwise, the right_child
pointer will point to the child and the left_child will point to NULL.
● The root node does not have a parent. So its parent pointer will point to
NULL. Among all the nodes, only the root node does not have a parent.
Binary Tree Traversal
What is Traversal?
Traversing means passing through all the nodes in a specific order.

There are four types of binary tree traversal.

1. Preorder traversal
2. Inorder traversal
3. Postorder traversal
4. Level-order traversal

Among these four, the first three are mostly practiced.

Recursive Algorithm
Before starting traversal algorithms, we need to know what is recursive
algorithm. Think of the following example.

Let us find out 5^7.

5^4 = 5 x 5^3

= 5 x 5 x 5^2

= 5 x 5 x 5 x 5^1

= 5 x 5 x 5 x 5 x 5^0
Base Case of a Recursive Algorithm
When we reach at the last line in the previous slide, we found 5^0.

If we have this value, then we can go back each line computing the result and
eventually find out the value of 5^4!

What is the value of 5^0? We know that any number in its zero power results 1

So, 5^0 = 1

If we go back to our problem again to find out the value of 5 to the power of 4,
we get,
Base Case of a Recursive Algorithm
5^4 = 5 x 5 x 5 x 5 x 1

=5x5x5x5

= 5 x 5 x 25

= 5 x 125

= 625
Algorithm to solve this type of Recursion
Let, a function is power(n, e) where, n is the number and e is the exponent

So, power(5, 4) = 5 x power(5, 3)

= 5 x 5 x power(5, 2)

= 5 x 5 x 5 x power(5, 1)

= 5 x 5 x 5 x 5 x power(5, 0)

So, the base case will be, power (n, 0) which will return 1.
Recursive algorithm for Power(n, e)
So, power(5, 4) will call power(5, 3)
power(n, e)
power(5, 3) will call power(5, 2)
if (e==0) then
power(5, 2) will call power(5, 1)

return 1 power(5, 1) will call power(5, 0)

return (n*power(n, e-1)) power(5, 0) will return 1

power(5, 1) will return 5

power(5, 2) will return 25

power(5, 3) will return 125

power(5, 4) will return 625

Preorder Traversal
Preorder Traversal
Steps:

1. Visit the node

2. Traverse the left subtree using preorder(left_child)
3. Traverse the right subtree using preorder(right_child)
Algorithm
Preorder(Node n)

visit(n)

Preorder(n->left_child)

Preorder(n->right_child)
Example
preorder(1)

preorder(2)

preorder(3)

Traversal: 1
Example
preorder(2)

preorder(4)

preorder(5)

Traversal: 1, 2
Example
preorder(4)

preorder(8)

preorder(9)

Traversal: 1, 2, 4
Example
preorder(8)

preorder(NULL)

preorder(NULL)

Traversal: 1, 2, 4, 8
Example
preorder(9)

preorder(NULL)

preorder(NULL)

Traversal: 1, 2, 4, 8, 9
Example
preorder(5)

preorder(10)

preorder(11)

Traversal: 1, 2, 4, 8, 9, 5
Example
preorder(10)

10

preorder(NULL)

preorder(NULL)

Traversal: 1, 2, 4, 8, 9, 5, 10
Example
preorder(11)

11

preorder(NULL)

preorder(NULL)

Traversal: 1, 2, 4, 8, 9, 5, 10, 11
Example
preorder(3)

preorder(6)

preorder(7)

Traversal: 1, 2, 4, 8, 9, 5, 10, 11, 3

Example
preorder(3)

preorder(6)

preorder(7)

Traversal: 1, 2, 4, 8, 9, 5, 10, 11, 3

Example
preorder(6)

preorder(NULL)

preorder(13)

Traversal: 1, 2, 4, 8, 9, 5, 10, 11, 3, 6

Example
preorder(13)

13

preorder(NULL)

preorder(NULL)

Traversal: 1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 13

Example
preorder(7)

preorder(14)

preorder(NULL)

Traversal: 1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 13, 7

Example
preorder(14)

14

preorder(NULL)

preorder(NULL)

Traversal: 1, 2, 4, 8, 9, 5, 10, 11, 3, 6, 13, 7, 14

Preorder Algorithm
preorder(node n)

If (n->left_child == NULL) and (n->right_child == NULL) then

return

print n->data

preorder(n->left_child)

preorder(n->right_child)
Exercise 1
Print the preorder traversal of the given

tree.

Traversal: 2, 7, 2, 6, 5, 11, 5, 9, 4
Exercise 2
Print the preorder traversal of

the given tree.

Traversal: 7, 3, 1, 0, 2, 6, 4, 5, 12, 9, 8, 11, 10, 13, 15, 14

Postorder Traversal
Postorder Traversal
Steps:

1. Traverse the left subtree using preorder(left_child)

2. Traverse the right subtree using preorder(right_child)
3. Visit the node
Algorithm
Postorder(Node n)

Postorder(n->left_child)

Postorder(n->right_child)

visit(n)
Example
postorder(1)

postorder(2)

postorder(3)

visit 1

Traversal:
Example
postorder(2)

postorder(4)

postorder(5)

visit 2

Traversal:
Example
postorder(4)

postorder(8)

postorder(9)

visit 4

Traversal:
Example
postorder(8)

postorder(NULL)

postorder(NULL)

visit 8

Traversal: 8
Example
postorder(9)

postorder(NULL)

postorder(NULL)

visit 9

Traversal: 8, 9
Example

visit 4

Traversal: 8, 9, 4
Example
postorder(5)

postorder(10)

postorder(11)

visit 5

Traversal: 8, 9, 4
Example
postorder(10)

postorder(NULL)

postorder(NULL)

visit 10

Traversal: 8, 9, 4, 10
Example
postorder(11)

postorder(NULL)

postorder(NULL)

visit 11

Traversal: 8, 9, 4, 10, 11
Example

visit 5

Traversal: 8, 9, 4, 10, 11, 5

Example

visit 2

Traversal: 8, 9, 4, 10, 11, 5, 2

Example
postorder(3)

postorder(6)

postorder(7)

visit 3

Traversal: 8, 9, 4, 10, 11, 5, 2

Example
postorder(6)

postorder(NULL)

postorder(13)

visit 6

Traversal: 8, 9, 4, 10, 11, 5, 2

Example
postorder(13)

postorder(NULL)

postorder(NULL)

visit 13

Traversal: 8, 9, 4, 10, 11, 5, 2, 13

Example

visit 6

Traversal: 8, 9, 4, 10, 11, 5, 2, 13, 6

Example
postorder(7)

postorder(14)

postorder(NULL)

visit 7

Traversal: 8, 9, 4, 10, 11, 5, 2, 13, 6

Example
postorder(14)

postorder(NULL)

postorder(NULL)

visit 14

Traversal: 8, 9, 4, 10, 11, 5, 2, 13, 6, 14

Example

visit 7

Traversal: 8, 9, 4, 10, 11, 5, 2, 13, 6, 14, 7

Example

visit 3

Traversal: 8, 9, 4, 10, 11, 5, 2, 13, 6, 14, 7, 3

Example

visit 1

Traversal: 8, 9, 4, 10, 11, 5, 2, 13, 6, 14, 7, 3, 1

Exercise 1
Print the postorder traversal of the given

tree.

Traversal: 2, 5, 11, 6, 7, 4, 9, 5, 2
Exercise 2
Print the postorder traversal of

the given tree.

Traversal: 0, 2, 1, 5, 4, 6, 3, 8, 10, 11, 9, 14, 15, 13, 12, 7

Inorder Traversal
Inorder Traversal
Steps:

1. Traverse the left subtree using Inorder(left_child)

2. Visit the node
3. Traverse the right subtree using Inorder(right_child)
Algorithm
Inorder(Node n)

Inorder(n->left_child)

visit(n)

Inorder(n->right_child)
Example
inorder(1)

inorder(2)

visit 1

inorder(3)

Traversal:
Example
inorder(2)

inorder(4)

visit 2

inorder(5)

Traversal:
Example
inorder(4)

inorder(8)

visit 4

inorder(9)

Traversal:
Example
inorder(8)

inorder(NULL)

visit 8

inorder(NULL)

Traversal: 8
Example
inorder(4)

inorder(8)

visit 4

inorder(9)

Traversal: 8. 4
Example
inorder(9)

inorder(NULL)

visit 9

inorder(NULL)

Traversal: 8. 4, 9
Example
inorder(2)

inorder(4)

visit 2

inorder(5)

Traversal: 8. 4, 9, 2
Example
inorder(5)

inorder(10)

visit 5

inorder(11)

Traversal: 8. 4, 9, 2
Example
inorder(10)

inorder(NULL)

visit 10

inorder(NULL)

Traversal: 8. 4, 9, 2, 10
Example
inorder(5)

inorder(10)

visit 5

inorder(11)

Traversal: 8. 4, 9, 2, 10, 5
Example
inorder(11)

inorder(NULL)

visit 11

inorder(NULL)

Traversal: 8. 4, 9, 2, 10, 5, 11
Example
inorder(1)

inorder(2)

visit 1

inorder(3)

Traversal: 8. 4, 9, 2, 10, 5, 11, 1

Example
inorder(3)

inorder(6)

visit 3

inorder(7)

Traversal: 8. 4, 9, 2, 10, 5, 11, 1

Example
inorder(6)

inorder(NULL)

visit 6

inorder(13)

Traversal: 8. 4, 9, 2, 10, 5, 11, 1, 6

Example
inorder(13)

inorder(NULL)

visit 13

inorder(NULL)

Traversal: 8. 4, 9, 2, 10, 5, 11, 1, 6, 13

Example
inorder(3)

inorder(6)

visit 3

inorder(7)

Traversal: 8. 4, 9, 2, 10, 5, 11, 1, 6, 13, 3

Example
inorder(7)

inorder(14)

visit 7

inorder(NULL)

Traversal: 8. 4, 9, 2, 10, 5, 11, 1, 6, 13, 3

Example
inorder(14)

inorder(NULL)

visit 14

inorder(NULL)

Traversal: 8. 4, 9, 2, 10, 5, 11, 1, 6, 13, 3, 14

Example
inorder(7)

inorder(14)

visit 7

inorder(NULL)

Traversal: 8. 4, 9, 2, 10, 5, 11, 1, 6, 13, 3, 14, 7

Exercise 1
Print the postorder traversal of the given

tree.

Traversal: 2, 5, 11, 6, 7, 4, 9, 5, 2
Exercise 2
Print the postorder traversal of

the given tree.

Traversal: 0, 2, 1, 5, 4, 6, 3, 8, 10, 11, 9, 14, 15, 13, 12, 7

Thank You