Binary tree traversals
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.
There are three ways which we use to traverse a tree
- In-order Traversal
- Pre-order Traversal
- Post-order Traversal
Let's go through each of these traversals step by step:
1. In-Order Traversal
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.
In-Order Traversal Recursion and Non Recursion Algorithm
Steps:- Traverse the left subtree in an in-order manner.
- Visit the current node (e.g., print the node's data).
- Traverse the right subtree in an in-order manner.
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
2. Pre-Order Traversal
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.
Pre-Order Traversal Recursion and Non Recursion Algorithm
Steps:- Visit the current node (e.g., print the node's data).
- Traverse the left subtree in a pre-order manner.
- Traverse the right subtree in a pre-order manner.
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
3. Post-Order Traversal
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.
Post-Order Traversal Recursion and Non Recursion Algorithm
Steps:- Traverse the left subtree in a post-order manner.
- Traverse the right subtree in a post-order manner.
- Visit the current node (e.g., print the node's data).
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
Example tree traversals
Consider a tree with the structure:
A
/ \
B C
/ \ \
D E F
- In-Order: D, B, E, A, C, F
- Pre-Order: A, B, D, E, C, F
- Post-Order: D, E, B, F, C, A
Each traversal serves different purposes and offers a unique view of the elements in the binary tree.
Construction of a Binary Tree from its Traversals
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.
- If the preorder traversal is given, then the first node in the linear order is the root node. If the postorder traversal is given, then the last node is the root node.
- Once the root node is known, the nodes in the left subtree and the right subtree are established by using inorder sequence.
- The above two steps are repeated to form subtrees and finally the required binary tree.