Home Theory InOrder Traversal in a binary tree

InOrder Traversal in a binary tree

by nikoo28
0 comment

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:-
in_order_traversal_image(1)in_order_traversal_2inorder taversal image 3
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)
        // 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
		// If the root is not null
			// 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
		// 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

Time Complexity:- O(n)
Space Complexity:- O(n)

You can download the complete working code here.

You may also like

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More