Page 222 - DCAP407_DATA_STRUCTURE

Unit 12: Binary Tree Traversals and Operations

Figure 12.2 shows binary tree for preorder traversal.

Figure 12.2: Binary Tree for Preorder Traversal

In the figure 12.2, T1 is the root node, T2 and T3 are the sub-trees of the root node. The preorder
traversal for a binary tree traverses the root node first, then the left sub-tree and finally the right sub-
tree. Since the traversing process is in the order of root node, left and right sub-trees, let us assign the
alphabet N for visiting root node, L for visiting left sub-tree and R for visiting right sub-tree.
The term T1NLR indicates that node T1 is the root node of the binary tree and subscript NLR indicates
preorder tree traversal. The following represents the preorder traversal for binary tree present in the
figure 12.2
T1NLR---->T1 T2 NLR T3 NLR //After visiting T1NLR

---->T1 T2T4 NLRµ T3 NLR //After visiting T2NLR, µis empty child
---->T1 T2 T4T7NLR T8NLR T3NLR//After visiting T4NLR
----> T1 T2 T4 T7 µµT8NLR T3NLR//After visiting T7NLR ,µis empty left/right child
---->T1 T2 T4 T7 T8 µµT3NLR//After visiting T8NLR
---->T1 T2 T4 T7 T8 T3 T5NLRT6NLR//After visiting T3NLR
---->T1 T2 T4 T7 T8 T3 T5 µT9NLRT6NLR//After visiting T5

---->T1 T2 T4 T7 T8 T3 T5 T9 µµT6NLR//After visiting T9NLR
---->T1 T2 T4 T7 T8 T3 T5 T9 T6 µµ//After visiting T6NLR
---->T1 T2 T4 T7 T8 T3 T5 T9 T6
Hence, the preorder traversal for the tree shown in figure 12.2 is T1 T2 T4 T7 T8 T3 T5 T9 T6.
The traversal in preorder starts with traversing root, right sub-tree and left sub-tree. But this traversing
happens only during the downward movement of the traverse operation in a binary tree. If the upward
traversing is required in a tree, then it takes place in a reverse manner. To implement upward
traversing, a stack is required to save pointer variable during the tree traversal. This mode of traversing
is known as iterative traverse. The general form of iterative traversal for preorder using stack is as
follows:
Step 1: If the tree is empty //Check if the tree is empty

then (“empty tree”) // If tree is empty write “empty tree”
return
else
Place the pointer to the root of the tree on the stack// Move the pointer to the root of stack
Step 2: Repeat step 3 while stack is not empty.

LOVELY PROFESSIONAL UNIVERSITY 215