Binary Tree Inorder Traversal
Binary Tree Inorder Traversal is LeetCode 94 (Easy). Given the root of a binary tree, return its node values in inorder: the left subtree, then the node, then the right subtree.
- The tree can be empty; then the answer is
[]. - Follow-up: the recursive solution is trivial, so do it iteratively.
With at most 100 nodes any O(n) walk is fast; the real question is how to do it without recursion.
- The number of nodes in the tree is in the range [0, 100].
- -100 <= Node.val <= 100
Intuition
Recursion writes a binary tree inorder traversal in three lines but hides its bookkeeping in the call stack. An iterative inorder traversal keeps that bookkeeping in a stack of its own.
The rule behind it: a node can be output only after its whole left subtree. So every node passed on the way left has to wait, and the one passed last is the first one ready. Last in, first out is exactly what a stack gives, and it only ever holds one root-to-leaf path, so it needs O(h) space.
Inorder is the order to reach for on a binary search tree: left, node, right visits the values in ascending order. Validate BST, Kth Smallest Element in a BST, Recover BST and BST Iterator are all this traversal with a check in place of the append. The stack loop is also exactly how a BST iterator pauses between calls to next().
Approach
Before reading on: in the tree [1,2,3,4,5], which nodes are still waiting at the moment 4 is output, and in what order must they come out? Which data structure hands them back in that order?
Two ways to solve it
A stack holds the nodes still waiting for their left side to finish.
- Follow-up: the iterative answer LeetCode asks for.
- Depth: no recursion limit on a chain-shaped tree.
- Reuse: the same loop drives a BST iterator.
The version to know for interviews.
A helper recurses left, appends the node, then recurses right.
- Code: three lines that mirror the definition.
- Memory: the call stack holds one path.
- Limit: a very deep tree can hit the recursion limit.
Fine when recursion is allowed and the tree is shallow.
Both visit each node once in O(h) memory, but the stack version answers the follow-up and has no recursion-depth limit, so the steps, code and live demo follow it. The recursive code comes after the demo.
Walk left, pushing every node
From node, push it and move to node.left, until node is empty. Each pushed node is waiting for its left subtree to finish first.
Pop and record
When node is empty, pop the top of the stack and append its value. Everything to its left is already in the answer, because its left subtree was finished before it reached the top again.
Move to the right child
Set node = node.right and go back to the first step. The right subtree comes after the node in inorder and is handled like a fresh tree. If it is empty, the next pop returns the nearest ancestor still waiting.
Stop when both are empty
The loop runs while node or the stack is non-empty. Each node is pushed once and popped once, so the walk is O(n) time, and the stack holds at most one root-to-node path, O(h) space.
Binary Tree Inorder Traversal solution in Python | C++ | Java
node becomes empty and the inner loop stops: nothing is left to the left of 1.node moves to 2 and the walk-left loop starts again from there.node becomes empty and the inner loop stops: nothing is left to the left of 3.node is empty and so is the stack. Every node was pushed once and popped once, and each was popped only after its entire left subtree, which is exactly inorder.node becomes empty and the inner loop stops: nothing is left to the left of 4.node moves to 5 and the walk-left loop starts again from there.node becomes empty and the inner loop stops: nothing is left to the left of 6.node moves to 7 and the walk-left loop starts again from there.node becomes empty and the inner loop stops: nothing is left to the left of 7.node moves to 3 and the walk-left loop starts again from there.node becomes empty and the inner loop stops: nothing is left to the left of 3.node moves to 8 and the walk-left loop starts again from there.node becomes empty and the inner loop stops: nothing is left to the left of 8.node is empty and so is the stack. Every node was pushed once and popped once, and each was popped only after its entire left subtree, which is exactly inorder.node starts as nothing and the stack is empty, so the loop condition is false straight away and the answer is an empty list. No special case is needed.Recursive inorder traversal
dfs(node) returns at once on an empty node; otherwise it visits the left subtree, appends node.val, then visits the right subtree. The call stack does the job of the explicit stack.
Common pitfalls
Recording a node when it is pushed
while node:
result.append(node.val)
stack.append(node)
node = node.leftnode = stack.pop() result.append(node.val)
Appending on the way down outputs each node before its left subtree, which is preorder. For [1,2,3] it gives [1, 2, 3] instead of [2, 1, 3].
Looping only while the stack is non-empty
while stack:
while node or stack:
The stack is empty at the start and again right after the root is popped, yet node still has work: first the root itself, later the root's right subtree. while stack stops at those moments and returns too little.
Building the answer by list concatenation
return dfs(node.left) + [node.val] + dfs(node.right)
result.append(node.val) # one shared list
In a binary tree inorder traversal Python solution written this way, each + copies the lists built so far. On a chain-shaped tree that is O(n²) work; appending to one list is O(1) per node.
Edge cases
node starts as None and the stack is empty, so the loop never runs and the answer is [].
Every node is pushed before the first pop, so the stack grows to n: the O(h) space bound is O(n) in the worst case.
Complexity
Binary Tree Inorder Traversal FAQ
Can LeetCode 94 be solved in O(1) extra space?
Yes, with Morris traversal. Before going left, it links the rightmost node of the left subtree back to the current node, follows that link to come back up, and then removes it. Time stays O(n) and the tree is restored by the end.