Binary Tree Traversal
Order of Traversal of Binary Tree
The following are the possible orders in which a binary tree can be traversed:
LDR
LRD
DLR
RDL
RLD
DRL
where L stands for traversing the left subtree, R stands for traversing the right subtree, and D stands for processing the data of the node. Therefore, the order LDR is the order of traversal in which we start with the root node, visit the left subtree, process the data of the root node, and then visit the right subtree. Since the left and right subtrees are also the binary trees, the same procedure is used recursively while visiting the left and right subtrees.
The order LDR is called as inorder; the order LRD is called as postorder; and the order DLR is called as preorder. The remaining three orders are not used. If the processing that we do with the data in the node of tree during the traversal is simply printing the data value, then the output generated for a tree is given in following Figure, using inorder, preorder and postorder as shown.
If an expression is represented as a binary tree, the inorder traversal of the tree gives us an infix expression, whereas the postorder traversal gives us a postfix expression as shown in following Figure.
<
Given an order of traversal of a tree, it is possible to construct a tree; for example, consider the folowing order:
Inorder = DBEAC
We can construct the binary trees shown in following Figure by using this order of traversal:
Therefore, we conclude that given only one order of traversal of a tree, it is possible to construct a number of binary trees; a unique binary tree cannot be constructed with only one order of traversal. For construction of a unique binary tree, we require two orders, in which one has to be inorder; the other can be preorder or postorder. For example, consider the following orders:
Inorder = DBEAC
Postorder = DEBCA
We can construct the unique binary tree shown in following Figure by using these orders of traversal:
