Problem

Given a binary tree, write a non recursive or iterative algorithm for Inorder traversal.

Inorder Traversal

  1. First, visit all the nodes in the left subtree
  2. Then the root node
  3. Visit all the nodes in the right subtree
inorder(root->left)
display(root->data)
inorder(root->right)

Example

Example 1:

   1
    \
     2
    /
   3

Input: root = [1,null,2,3]
Output: [1,3,2]

Example 2:

graph TD;
1 --- 2 & 3
2 --- 4 & 5
3 --- 6 & 7
  
Input: root = [1,2,3,4,5, 6, 7]
Output: [4, 2, 5, 1, 6, 3, 7]

Follow up

Using recursion is not allowed.

There are 3 solutions for solving this problem.

Solution

This is how the inorder traversal looks:

Method 1 - Recursive

The recursive solution is trivial.

public List<Integer> inorderTraversal(TreeNode root) {
	List<Integer> ans = new ArrayList<>();
	if (root == null) {
		return ans;
	}
	helper(root, ans);
}

private void helper(TreeNode root, List<Integer> ans) {
	if (root == null) {
		return;
	}
	helper(root.left, ans);
	ans.add(root.val);
	helper(root.right, ans);
}

Complexity

  • ⏰ Time complexity: O(n), as each node is visited once.
  • 🧺 Space complexity: O(n) (using recursive stack)

Method 2 - Iterative Approach - Morris Traversal

Morris Traversal

Complexity

  • ⏰ Time complexity: O(n), as each node is visited once.
  • 🧺 Space complexity: O(1)

Method 3 - Iterative Using Stack

The key to solve inorder traversal of binary tree includes the following:

  1. The order of “inorder” is: left child -> parent -> right child
  2. Use a stack to track nodes
  3. Understand when to push node into the stack and when to pop node out of the stack

Here is the pushing order of nodes in stack:

Dry Run

Code

Java
public ArrayList < Integer > inorderTraversal(TreeNode root) {
    List<Integer> ans = new ArrayList<> ();

    if (root == null) {
	    return list;
	}

    Stack<TreeNode> stack = new Stack <>();

    TreeNode curr = root;

    while (!stack.isEmpty() || curr != null) {
        if (curr != null) {
            stack.push(curr);
            curr = curr.left;
        } else {
            TreeNode t = stack.pop();
            ans.add(t.val);
            curr = t.right;
        }
    }

    return ans;
}

We can also write code like this:

public List<Integer> inorderTraversal(TreeNode root) {
	List<Integer> ans = new LinkedList<Integer>();
	if (root == null) {
		return ans;
	}
	
	Stack<TreeNode> stack = new Stack<TreeNode>();
	TreeNode cur = root;
	while (cur != null || !stack.isEmpty()) { 
		while (cur != null) {// Travel to each node's left child, till reach the left leaf
			stack.push(cur);
			cur = cur.left;				
		}		 
		cur = stack.pop(); // Backtrack to higher level node A
		ans.add(cur.val);  // Add the node to the result list
		cur = cur.right;   // Switch to A'right branch
	}
	return ans;
}

Complexity

  • ⏰ Time complexity: O(n), as each node is visited once.
  • 🧺 Space complexity: O(n)

Method 4 - Using Stack with Tree Modification

public List<Integer> inorderTraversal(TreeNode root) {
	List<Integer> ans = new ArrayList<Integer>();

	if (root == null) {
		return ans;
	}

	Stack<TreeNode> stack = new Stack<>();
	stack.push(root);

	while (!stack.isEmpty()) {
		TreeNode top = stack.peek();

		if (top.left != null) {
			stack.push(top.left);
			top.left = null; // modifying the tree
		} else {
			ans.add(top.val);
			stack.pop();

			if (top.right != null) {
				stack.push(top.right);
			}
		}
	}

	return ans;
}