We discussed about the tree traversal techniques in this post-
Please see pre-order traversal to understand the basics of visiting nodes. We have our same sample tree
Now let us try to understand the In-order traversal. In in-order traversal, the root is traversed between the sub trees. In-order traversal is defined as follows.
- Traverse the left sub-tree
- Visit the node
- Traverse the right sub-tree
So when we apply the in-order traversal on our example tree this will be done as:-
We get the final in-order traversal as:- 4, 2, 5, 1, 6, 3, 7
The recursive version of in-order traversal can be written as:-
void inOrderRecursive(struct binaryTreeNode * root)
{
if(root)
{
// In-order traversal of left sub-tree (Step 1)
inOrderRecursive(root -> left);
// Visit the root (Step 2)
printf("%d ", root -> data);
// In-order traversal of right sub-tree(Step 3)
inOrderRecursive(root -> right);
}
}
Non-Recursive In-order Traversal
Non-recursive version of In-order traversal us very much similar to Pre-order. The only change is instead of processing the node before going to left sub-tree, process it after popping (which indicates after completion of left sub-tree processing).
void inOrderNonRecursive(struct binaryTreeNode * root)
{
// Create a new empty stack
struct stackNode * S = NULL;
// We need to loop until the stack is empty
while(1)
{
// If the root is not null
while(root)
{
// Push the first element onto the stack
S = push(S, root);
// Go to left sub-tree and keep on adding it to the stack
root = root -> left; // (Step 1)
}
// Check if the stack is empty
if(isStackEmpty(S))
break;
// else we need to pop out the element
root = S -> data;
// Remove the element from the stack
S = S -> next;
// After popping process the current node
printf("%d ",root -> data); // Step 2
// After printing, left sub-tree and root have been completed
// Go to the right sub-tree
root = root -> right; // Step 3
}
// We need to delete the stack
free(S);
}
Time Complexity:- O(n)
Space Complexity:- O(n)