~20 minutes · Day 31 · tree recursion · Python
Tonight starts trees with Binary Tree Inorder Traversal. Interviewers use this problem because it reveals whether you can stop thinking of data as a straight line. A tree has branches, so the skill is choosing a visiting order and trusting that order at every node.
Inorder means: fully visit the left subtree, then this node, then the right subtree — recursion does the bookkeeping for you.
A tree traversal is simply a rule for visiting the nodes of a tree in an order (Wikipedia: tree traversal). LeetCode gives you the root of a binary tree and asks for the inorder list of node values (LeetCode: Binary Tree Inorder Traversal).
The small numbers show the append order: finish the whole left subtree before appending the root.
A beginner brute force is to copy the sample shape: left child, root, right child. It is O(1) for this tiny shape only, which is exactly the problem: it is not a real solution for deeper trees.
def inorder_one_level(root):
if not root:
return []
ans = []
if root.left:
ans.append(root.left.val)
ans.append(root.val)
if root.right:
ans.append(root.right.val)
return ans
This fails as soon as root.left has its own children. The missing idea is not more if statements. The missing idea is: treat every subtree as the same kind of problem.
At each node, do exactly three things in order: solve the left subtree, record this node, solve the right subtree. The function does not need to remember the path back manually; the recursive call stack remembers it.
The recursion is not extra memory work you write by hand; each call returns to the paused node at the exact next step.
def inorderTraversal(root):
ans = []
def dfs(node):
if not node:
return
dfs(node.left) # fully visit the left subtree
ans.append(node.val) # then visit this node
dfs(node.right) # then fully visit the right subtree
dfs(root)
return ans
Read the code as the invariant, not as magic. If node is empty, there is nothing to visit. Otherwise, the left side finishes first, then the current value is appended, then the right side finishes.
The LeetCode follow-up asks whether you can do the traversal iteratively. Before opening the reveal: if recursion was remembering paused nodes for you, what structure should remember those paused nodes explicitly?
Use a stack. Push nodes while walking left. When there is no more left child, pop the most recent paused node, visit it, then move to its right subtree.
def inorder_iter(root):
ans, stack = [], []
cur = root
while cur or stack:
while cur:
stack.append(cur) # pause node until left is done
cur = cur.left
cur = stack.pop()
ans.append(cur.val) # left done; visit node
cur = cur.right # now handle the right subtree
return ans
| Approach | Time | Space |
|---|---|---|
| Brute force shape cases | O(1) for one shape only | O(1) |
| Recursive inorder traversal | O(n) | O(h) stack + O(n) output |
Here n is the number of nodes and h is the tree height. A correct traversal must touch every node, so O(n) time is the target.
1. Which phrase describes inorder traversal?
2. What is the recursive base case?
3. Spot the bug for inorder:
def dfs(node):
if not node:
return
ans.append(node.val)
dfs(node.left)
dfs(node.right)4. Which task is tonight's assignment?
Solve Binary Tree Inorder Traversal in your Notion tracker with the cycle — predict → attempt → compare → encode.
Watch the NeetCode solution video on NeetCode — Binary Tree Inorder Traversal after your attempt, as the compare step. Listen for how the explanation separates left subtree, current node, and right subtree.