On this page

Iterative Inorder Traversal

Do the inorder traversal (Left, Root, Right) of a binary tree without recursion. Return the node values as a list.

This is the iterative version of Binary Tree Inorder Traversal (LeetCode 94), and the basis for the BST Iterator problem later in this track.

Intuition

Every example below uses this tree:

1 1
2 / \
3 2 3
4 / \ \
5 4 5 6

Inorder cannot visit a node until its entire left subtree is done. So from any node we first walk as far left as we can, remembering the path on a stack. The node on top of the stack is then the leftmost unvisited node, which is exactly the next one to record.

After recording it, the next candidate is its right subtree, and we repeat the same "go left as far as possible" idea there.

Approach: Walk Left, Pop, Go Right

Keep a pointer node, starting at the root, and a stack.

  1. While node is not null, push it and move to node.left. This pushes the whole left spine.
  2. When node becomes null, the stack top is the next node in inorder. Pop it and add its value.
  3. Move to its right child and repeat from step 1.
  4. Stop when node is null and the stack is empty.

Dry run on the sample tree:

  • Go left: push 1, push 2, push 4. Stack [1, 2, 4].
  • Pop 4, answer [4]. Its right is null.
  • Pop 2, answer [4, 2]. Go right to 5, push it. Pop 5, answer [4, 2, 5].
  • Pop 1, answer [4, 2, 5, 1]. Go right to 3, push it. Pop 3, answer [4, 2, 5, 1, 3].
  • Go right to 6, push it. Pop 6, answer [4, 2, 5, 1, 3, 6].

Code

class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
vector<int> ans;
stack<TreeNode*> st;
TreeNode* node = root;
while (node != nullptr || !st.empty()) {
while (node != nullptr) {
st.push(node);
node = node->left;
}
node = st.top();
st.pop();
ans.push_back(node->val);
node = node->right;
}
return ans;
}
};

Complexity

Time: O(n)

Each node is pushed once and popped once.

Space: O(h)

The stack holds the current left spine, at most the tree height. O(n) for a skewed tree.

How to Explain It in an Interview

How to Explain it in an Interview

The 30-Second Spoken Pitch
"Inorder needs the whole left subtree first, so I keep a pointer and a stack. While the pointer is not null I push it and go left, which stacks up the left spine. When I hit null, the top of the stack is the next node in inorder, so I pop it, record its value, and move to its right child. Then I repeat. I stop when the pointer is null and the stack is empty. Each node is pushed and popped once, so time is O of n, and the stack holds at most one root-to-leaf path, so space is O of h."
Next TopicIterative Postorder Traversal (Two Stacks)