CREATE OWN LIBRARY
Binary tree traversal using recursion.
Back to ProgrammingDescription
A binary tree is a special tree, where every node can have at most two children. One node designated as the root marks the beginning of the binary tree. In a binary tree, the child node on the left is called ‘left child node’ and the child node on the right is called the ‘right child node’.
A binary tree can either be empty or it may comprise a node called the ‘root’, a left sub-binary tree and right sub-binary tree, both of which acts like a binary tree.
Tree traversal is the process to visit each and every node of a tree and display their values. There are three ways to traverse a binary tree
(a) In-order traversal
(b) Pre-order traversal
(c) Post-order traversal
(a) In-order traversal:
In in-order traversal, the left sub-tree is visited first, then the root node followed by the right sub-tree. Every sub-tree is again considered to be a binary tree.
Let us consider an example, in Fig 2, ‘5’ is the root node of the binary tree. In in-order traversal, at first the left sub-tree is considered , then the root node followed by the right sub-tree, untill all the nodes have been visited.
Thus the in-order traversal of the binary tree in Fig 2 will be - 1, 2, 3, 5, 6, 4.
(a) Pre-order traversal:
In pre-order traversal, the root node is visited first, then the left sub-tree followed by the right sub-tree. Every sub-tree is again considered to be a binary tree.
Let us consider an example, in Fig 2, ‘5’is the root node of the binary tree. In pre-order traversal, at first the root node is considered , then the left sub-tree followed by the right sub-tree, untill all the nodes have been visited.
Thus the pre-order traversal of the binary tree in Fig 2 will be - 5, 2, 1, 3, 6, 4
(c) Post-order traversal:
In post-order traversal, the left sub-tree is visited first, then the right sub-tree followed by the root node . Every sub-tree is again considered to be a binary tree.
Let us consider an example, in Fig 2, ‘5’ is the root node of the binary tree. In post-order traversal, at first the left sub-tree is considered , then the right sub-tree followed by the root node, untill all the nodes have been visited.
Thus the post-order traversal of the binary tree in Fig 2 will be 1, 3, 2, 4, 6, 5.
Algorithm
Algorithm:
Input:
root which points to the root of the binary tree.
Output:
Binary Tree creation and then printing the tree in preorder, postorder and inorder using recursion.
Algo:
Step 1: Start
Step 2: Defining the create() function
l Enter the value of the node.
l Set temp[data] <= value.
l If left child of the node exists then,
(a) Set temp[left] <= create().
l If right child of the node exists then,
(a) Set temp[right] <= create().
l Return temp.
Step 3: Defining the preorder(temp) function
l If temp != NULL then,
(a) Display temp[data].
(b) Call preorder(temp[left]).
(c) Call preorder(temp[right]).
Step 4: Defining the inorder(temp) function
l If temp != NULL then,
(a) Call inorder(temp[left]).
(b) Display temp[data].
(c) Call inorder(temp[right]).
Step 5: Defining the postorder(temp) function
l If temp != NULL then,
(a) Call postorder(temp[left]).
(b) Call postorder(temp[right]).
(c) Display temp[data].
Step 6: Stop
Code
Application:
Binary tree traversal has many applications in various fields where the data has a hierarchical relationship. Some of its applications are
l In routers to retrieve data from routing tables.
l In compilers to parse expressions or syntax analysis.
Advantages:
The advantage of binary tree traversal is that it provides with an efficient means to traverse every node in the binary tree.
Disadvantages:
The binary tree traversal has many disadvantages
l Tree traversal using the iterative process takes help of the stack data structure which makes its implementation complicated.
l A binary tree has many ways in which it can be traversed, thus restricting its traversal means compromising with the flexibility of the binary tree.
Complexity:
Time Complexity:
In a binary tree, to traverse every node, we have to visit every node in the binary tree, thus time complexity for all traversals (i.e. preorder, preorder, postorder) in a binary tree with ‘n’ number of nodes is O(n).
Space Complexity:
In a binary tree with‘n’number of nodes, the space complexity will be O(n).
