Representation and traversal of a Binary Tree.
6.1 BINARY TRE.
A
A
s already seen in Chapter 2, a tree is a minimally connected graph without a circuit. For a graph
with n vertices to be minimally connected there have to be n-1 edges. A tree is, therefore, a
connected graph with n vertices and (n-1) edges. It can also be said to be a graph with n vertices
and (n-1) edges without a circuit.
Sometimes a specific node is given importance. Then, it is called a “rooted” tree. This tree is a
collection of vertices and edges in which a vertex has been identified as the root and the remaining
vertices are categorized into many classes (k >= 0), where each class is a rooted tree. Such a rooted tree
class is called the sub-tree of the given tree.
(b)
(a) (c)
Fig. 6.1 (a) A complete binary tree (b) A full binary tree (c)A binary tree showing levels binary tree
Chapter 6 - Representation and Traversal of a Binary Tree
BSIT 41 Algorithms
59
In the above definition if k is restricted to be maximum of 2 then the rooted tree is called “binary
tree”. If k = 0, it implies that there are no children. A node without any children is called a “leaf” node.
The number of levels in the tree is called the “depth” of the tree. A “complete” binary tree is one
which allows sequencing of the nodes and all the previous levels are maximally accommodated before the
next level is accommodated. i.e., the siblings are first accommodated before the children of any one of
them. And a binary tree which is maximally accommodated with all leaves at the same level is called
“full” binary tree. A full binary tree is always complete but complete binary tree need not be full. Fig. 6.1
(a) and (b) shows the examples for complete and full binary trees.
The maximum number of vertices at each level in a binary tree can be found out as follows:
At level 0: 20 number of vertices
At level 1: 21 number of vertices
At level 2: 22 number of vertices
…
At level i: 2i number of vertices
Therefore, maximum number of vertices in a binary tree of depth ‘l’ is:
012 3
2l
2 +2 + 2 + 2 + ... +
kl+1
i.e., å2 = 2 -1
0£k£1
A binary indicating the levels is shown in Fig. 6.1 (c)
6.2 REPRESENTATION OF A BINARY TRE.
Binary Tree can be represented using the two methods:
.
Static allocation, and
.
Dynamic allocation
In static allocation, we have two ways of representing the binary tree. One is through the use of
Adjacency matrices and the other through the use of Single dimensional array representation.
6.2.1 Adjacency Matrix Representatio.
A two dimensional array can be used to store the adjacency relations very easily and can be used to
represent a binary tree. In this representation, to represent a binary tree with n vertices we use a n×n
Chapter 6 - Representation and Traversal of a Binary Tree
matrix. Here the row indices correspond to the parent nodes and the column corresponds to the child
nodes. i.e., A row corresponding to the vertex vi having the entries ‘L’ and ‘R’ indicate that vi has as its
left child the index corresponding to the column with the entry ‘L’ and the index corresponding to the
column with ‘R’ entry as its right child. The column with no entries corresponds to the root node. All other
columns have only one element. Each row may have 0, 1 or 2 entries. Zero entry in the column indicates
that the node is the root. Zero entry in the row means that, that element is a leaf node, only one entry
means that the node has only one child and two entries denote that the node has both the children. “L” is
used to represent left child and “R” is used to represent right child entries.
Fig. 6.2 A Binary tree
The adjacency matrix representation for the binary tree shown in Fig. 6.2 is given below.
A B C D E F G H I J K
A L R
B L R
C L
D
E L R
F R
G
H
I L R
J
K
Now, let us see the space utilization of this method of binary tree representation. Let ‘n’ be the number
of vertices. There is space allocated for n x n matrix. i.e., we have n2 space allocated, but we have only
n-1 entries in the matrix. Therefore, the percentage of space utilization is given as follows:
BSIT 41 Algorithms
61
n -11
2 @ n =´100%
nn
The space utilization decreases as n increases. For large ‘n’, the percentage of utilization becomes
negligible. This is, therefore, not the most efficient method of representing a binary tree.
6.2.2 Single Dimensional Array Representatio.
Since the two dimensional array is a sparse matrix, we can consider the prospect of mapping it onto a
single dimensional array for better space utilization. In this representation, we have to note the following
points:
.
The left child of the ith node is placed at the 2ith position.
.
The right child of the ith node is placed at the (2i+1)th position.
.
The parent of the ith node is at the (i/2) th position in the array.
Thus the single dimensional array representation for the binary tree shown in Fig.6.2 turns out to be as
follows.
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
D E F G H I J K
If l is the depth of the binary tree then, the number of possible nodes in the binary tree is 2l+1-1. Hence
it is necessary to have 2l+1-1 locations allocated to represent the binary tree.
If ‘n’ is the number of nodes, then the percentage of utilization is
n -1
´100
l+1
2 - l
For a complete and full binary tree, there is 100% utilization and there is a maximum wastage if the
binary tree is right skewed or left skewed, where only l+1 spaces are utilized out of the 2l+1 – 1 spaces
possible.
l +1
i.e., ´100 is the worst possible utilization in the single dimensional array representation.
l +1
2 -1
An important observation to be made here is that the organization of the data in the binary tree decides
the space utilization of the representation used.
The other alternative way of representing the binary tree is based on Linked Allocation (dynamic
allocation method).
Chapter 6 - Representation and Traversal of a Binary Tree
6.2.3 Linked Representatio.
Here, the ‘structure’ for each node becomes regular and in each node structure, there is a pointer to
a left child and another to the right child and space for the data of that node. This is pictorially represented
below:
Lchild Data Rchild
Fig. 6.3 Linked representation of a binary tree
A binary tree represented using the linked representation is shown in Fig. 6.3. In this representation,
ordering of nodes is not mandatory and we require a header to point to the root node of the binary tree. If
there are ‘n’ nodes to be represented, only ‘n’ node-structures will be allocated. This means that there
will be 2n link fields. Out of 2n link fields only (n-1) will be actually used to point to the next nodes and the
remaining are wasted.
Therefore the percentage of utilization is given as:
n -11
=´100 = 50%
2nn
6.3 TRAVERSAL OF A BINARY TRE.
Traversal is the most important operation done on a binary tree. Traversal is the process of visiting all
the vertices of the tree in a systematic order. Systematic means that every time the tree is traversed it
should yield the same result.
BSIT 41 Algorithms
There are three major methods of traversals and the rest are reversals of them. They are:
1. Pre-order traversal
2. In-order traversal
3. Post-order traversal
Pre-Order Traversal
In this traversal, the nodes are visited in the order of root, left child and then right child. i.e.,
1 Visit the root node first.
2 Go to the first left sub-tree.
3 After the completion of the left sub-tree, Go to the right sub-tree.
Here, the leaf nodes represent the stopping criteria. We go to the sibling sub-tree after the traversal of
a sub-tree. The pre-order traversal sequence for the binary tree shown in Fig. 6.3 is : A B D E G H C F
I J K
In-Order Traversa.
In this traversal, the nodes are visited in the order of left child, root and then right child. i.e., the left
sub-tree is traversed first, then the root is visited and then the right sub-tree is traversed. Here also, the
leaf nodes denote the stopping criteria. The in-order traversal sequence for the above considered example
(Fig. 6.3) is: D B G E H A F J I K C
Post_Order Traversa.
In this traversal, the nodes are visited in the order of left child, right child and then root. i.e., the left
sub-tree is traversed first, then the sibling is traversed next. The root is visited last. The post-order
traversal for the above example (Fig. 6.3) is: D G H E B J K I F C A
6.3.1 Traversal of a Binary Tree Represented in an Adjacenc.
Matri.
The steps involved in traversing a binary tree from the adjacency matrix representation, firstly requires
to find out the root node. Then it entails to traverse through the left subtree and then the right subtree in
specific orders. In order to remember the nodes already visited it is necessary to maintain a stack data
structure. Thus, following are the steps involved in traversing trough the binary tree given in an adjacency
matrix representation.
1 Locate the root (the column sum is zero for the root)
2 Display
Chapter 6 - Representation and Traversal of a Binary Tree
3 Push in to the stack
4 Scan the row in search of ‘L’ for the left child information
5 Pop from the stack
6 Scan the row in search of ‘R’ for the right child information
7 Check if array IsEmpty().
8 Stop
Sequencing the above stated steps helps us in arriving at preorder, inorder and postorder traversal
sequences.
Preorder Traversa.
Fig.6.4 shows flow graph of preorder traversal.
‘L’ found
Fig. 6.4 Preorder flow graph
Note that before popping, we need to check whether the stack is empty or not.
Inorder Traversal
The in-order traversal will also have the same steps explained above. Only the flow graph sequence
changes, and is given in Fig. 6.5.
BSIT 41 Algorithms
Fig. 6.5 Inorder flow graph
Designing a flow graph for post order traversal is left as an exercise to the students.
6.3..
Binary Tree Traversal from one Dimensaional Arra.
Representatio.
Preorder Traversa.
Algorithm: Preorder Traversal
Input: A[], one dimensional array representing the binary tree
i, the root address //initially i=1
Output: Preorder sequence
Method:
If (A[i] != 0)
Display(A[i])
Preorder Traversal (A, 2i)
Preorder Traversal (A, 2i +1)
If end
Algorithm ends
Chapter 6 - Representation and Traversal of a Binary Tree
Inorder Traversa.
Algorithm: Inorder Traversal
Input: A[], one dimensional array representing the binary tree
i, the root address //initially i=1
Output: Inorder sequence
Method:
If (A[i] != 0)
Inorder Traversal (A, 2i)
Display(A[i])
Inorder Traversal (A, 2i +1)
If end
Algorithm ends
Postorder Traversa.
Algorithm: Postorder Traversal
Input: A[], one dimensional array representing the binary tree
i, the root address //initially i=1
Output: Postorder sequence
Method:
If (A[i] != 0)
Postorder Traversal (A, 2i)
Postorder Traversal (A, 2i +1)
Display(A[i])
If end
Algorithm ends
We shall now look into the tree traversals in linked representation
BSIT 41 Algorithms
6.3.3 Binary Tree in Linked Representatio.
As we already studied, every node has a structure which has links to the left and right children. The
algorithms for traversing the binary tree in linked representation are given below.
Algorithm: Pre-order Traversal
Input: bt, address of the root node
Output: Preorder sequence
Method:
if(bt != NULL)
{
Display([bt].data)
Pre-order Traversal([bt].Lchild)
Pre-order Traversal([bt].Rchild)
}
Algorithm ends.
Algorithm: In-order Traversal
Input: bt, address of the root node
Output: Inorder sequence
Method:
if(bt != NULL)
{
In-order Traversal([bt].Lchild)
Display([bt].data)
In-order Traversal([bt].Rchild)
}
Algorithm ends.
Chapter 6 - Representation and Traversal of a Binary Tree
Algorithm: Post-order Traversal
Input: bt, address of the root node
Output: Postorder sequence
Method:
if(bt != NULL)
{
Post-order Traversal([bt].Lchild)
Post-order Traversal([bt].Rchild)
Display([bt].data)
}
Algorithm ends.
SUMMAR.
In this chapter the binary trees are introduced. Trees form the core of non-linear data structure and
Binary tree helps in storing the data more efficiently although the access is not as simple as arrays. The
various ways of representing the binary tree, linear, two dimensional arrays and linked representation are
discussed. The algorithms for traversing the binary tree represented in various representations are also
presented.
EXERCIS.
1.
What is a binary tree
2.
Differentiate complete and full binary trees
3.
What is the maximum number of nodes in a binary tree of level 7, 8 and 9
4.
What are the wastage of memory for a binary tree with 16 nodes represented in a 1D array, 2D array and a linked
representation.
5.
For a atleast 5 binary trees of different depths greater than or equal to 6 of your choice obtain the preorder,
postorder and inorder sequences.