This post is completed by 1 user

  • 0
 Add to List
Beginner

180. Binary Tree-Inorder Traversal - Non Recursive Approach

Objective: Write a non-recursive or iterative algorithm for Inorder traversal given a binary tree.

Example:

Tree Traversals - Inorder

Earlier we have seen "What is Inorder traversal and recursive algorithm for it", In this article, we will solve it in an iterative/non-recursive manner.

Since we are not using recursion, we will use the Stack to store the traversal, we need to remember that inorder traversal, first traverse the left node then the root followed by the right node.

Pseudo Code:

	Create a Stack.
	Push the root into the stack and set the root = root.left continue till it hits the NULL.
	If the root is null and Stack is empty Then
		return, we are done.
	Else
		Pop the top Node from the Stack and set it as, root = popped_Node.
		print the root and go right, root = root.right.
		Go to step 2.
	End If

See the animated image below and code for more understanding.

Inorder Traversal - Non Recursive Approach
 

Output:

4 2 5 1 3
4 2 5 1 3

Related Problems: