Page 207 - DCAP201_FUNDAMENTALS_OF_DATA_STRUCTURES

Fundamentals of Data Structures

Notes To traverse a non-empty binary tree in post-order, we need to perform the following three
operations:

Traverse the left sub-tree in post-order.
Traverse the right sub-tree in post-order
Visit the root
In all the three methods nothing needs be done to traverse an empty binary tree.

Example:

Figure 12.7: Tree Traversal

Source: http://datastructures.itgo.com/trees/traversal.htm
In case of INORDER traversal, we start from the root, i.e. A. We are supposed to visit its left sub-
tree then visit the node itself and its right sub-tree. Here, A has a left sub-tree rooted at B. So, we
move to B and check for its left sub-tree. Again, B has a left sub-tree rooted at D. So, we check for
D’s left sub-tree now, but D doesn’t have any left sub-tree and thus we will visit node D first and
check for its right sub-tree. As D doesn’t have any right sub-tree, we’ll track back and visit node
B; and check for its right sub-tree. B has a right sub-tree rooted at E and so we move to E. Well,
E doesn’t have any left or right sub-trees so we just visit E and track back to B. We already have
visited B, so we track back to A. We are yet to visit the node itself and so we visit A first; then we
go for checking the right sub-tree of A, which is rooted at C. As C doesn’t have any left or right
tree we visit C. So, the INORDER becomes - D B E A C.
Similarly, in PREORDER, we visit the current node first, then we visit its left sub-tree and then
its right sub-tree. In POSTORDER, for every node, we visit the left sub-tree first and then the
right sub-tree and finally the node itself.

An algorithm is given as below:
1. Step-1: For the current node check whether it has a left child. If it has then go to step-2 or
else step-3.

2. Step-2: Repeat step-1 for this left child.
3. Step-3: Visit (i.e. printing in our case) the current node.
4. Step-4: For the current node check whether it has a right child. If it has then go to step-5.
5. Step-5: Repeat step-1 for this right child.

200 LOVELY PROFESSIONAL UNIVERSITY