InOrder Traversal in a binary tree

We discussed about the tree traversal techniques in this post-

• Binary Tree Traversals

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)

You can download the complete working code here.