Binary tree traversals are methods for visiting all the nodes in a binary tree in a specific order. There are several types of traversals, each serving different purposes.
Let's go through each of these traversals step by step:
In an in-order traversal, the nodes are traversed in a left-root-right order. This means that for any given node, you first visit its left subtree, then the node itself, and finally its right subtree.
Use Case: In a Binary Search Tree (BST), an in-order traversal retrieves the nodes in sorted order.
inorder (root)
if root ≠ NULL, then
inorder(root->left)
Print root → info
inorder(root->right)
inorder (root)
1. If root = NULL, then print "Empty tree" and exit.
2. top = -1 //Initialize stack top]
3. ptr = root. //Initialize ptr with root of the binary tree]
4. Repeat step 5, while stack is not empty or ptr ≠ NULL //Pushes left-most path onto stack]
5. If ptr ≠ NULL, then
a. Push(ptr) //[Push current node address onto stack]
b. ptr = ptr>left //Move ptr to left subtree]
Else:
C. ptr = popl //[Pop from stack, stored address and assign it to ptr
d. Print ptr → info //Print node data]
e. ptr = ptr→right //Move ptr to right subtree]
6. Exit
In a pre-order traversal, the nodes are traversed in a root-left-right order. This means that you visit the node first, then its left subtree, and finally its right subtree.
Use Case: Pre-order traversal is useful for creating a copy of the tree or for prefix notation expressions.
preorder (root)
if root ≠ NULL, then
Print root → info
preorder(root->left)
preorder(root->right)
preorder (root)
1. If root = NULL, then print "Empty tree" and exit.
2. top = -1 //[Initialize stack top]
3. Push(root) //[Push root address onto stack]
4. ptr = root. //[Initialize ptr with root of the binary tree]
5. Repeat steps 6 and 7, while stack is not empty
6. ptr = pop) //[Get stored address and assign to ptr]
7. If ptr ≠ NULL, then
(a) Print ptr→info //[Print node info]
(b) Push(ptr>right) //[Store address of right subtree]
(c) Push(ptr>left) //[ Store address of left subtree]
8. Exit
In post-order traversal, the nodes are traversed in a left-right-root order. Here, you first visit the left and right subtrees and then the node itself.
Use Case: Post-order traversal is used in deleting the tree or in postfix notation expressions.
postorder (root)
if root ≠ NULL, then
postorder(root->left)
postorder(root->right)
Print root → info
postorder (root)
1. If root = NULL, then print "Empty tree" and exit.
2. top = -1 //[Initialize stack topl
3. ptr = root. //[Initialize ptr with root of the binary tree]
4. tmp = NULL //[Initialize pointer variable, tmp to NULL]
5. Repeat steps 6 thru 8, while ptr> left ≠ NULL
6. Push (ptr)
7. ptr = ptr>left
8. Repeat steps a and b, while ptr ≠ NULL
a. If ptr>right = NULL or ptr>right = tmp
i. Print ptr> info
ii. tmp = ptr
iii. ptr = popl
b. Else:
i. Push(ptr)
ii. ptr = ptr>right
iii. Repeat steps (a) and (b), while ptr> left ≠ NULL
(a) Push(ptr)
(b) ptr = ptr->left
9. Exit
Consider a tree with the structure:
A
/ \
B C
/ \ \
D E F
Each traversal serves different purposes and offers a unique view of the elements in the binary tree.
It is sometimes necessary to construct (or reconstruct) a binary tree from its traversals. We require a minimum of two traversals to construct a unique binary tree. We need one of these two combinations:
A unique binary tree cannot be built with a combination of preorder and postorder traversals. The following is a procedure for construction of a binary tree.