Home Theory InOrder Traversal in a binary tree

# InOrder Traversal in a binary tree

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

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)

0 comment

#### You may also like

This site uses Akismet to reduce spam. Learn how your comment data is processed.

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