Page 111 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes where,
L stands for traversing the left sub-tree,
R stands for traversing the right sub-tree, 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 sub-tree fi rst, then process the data of the root node, and then go for visiting the right sub-
tree. Since the left, as well as right sub-trees are also the binary trees, the same procedure is used
recursively while visiting the left and right sub-trees.
The order LDR is called inorder, the order LRD is called postorder, and the order DLR is called
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 given below in Figure 5.9, using the inorder, preorder and postorder is the one shown
below in Figure 5.9 itself.
Figure 5.9: A Binary Tree along with its Inorder, Preorder and Postorder

A

B C

D E F G

H I

Different order path in Figure 5.9 are:

Inorder: DBHEIAFCG
preorder: ABDEHICFG
postorder: DHIEBFGCA
If an expression is represented as a binary tree then the inorder traversal of the tree gives us an
infi x expression, whereas the postorder traversal gives us posfi x expression as shown below in
Figure 5.10.

Figure 5.10: A Binary Tree of an Expression along with its Inorder and Postorder

+

+ *

a * d e

b c

106 LOVELY PROFESSIONAL UNIVERSITY