Binary Tree Inorder Traversal — Solution

Problem

Traverse a binary tree by visiting every node's left subtree first, then the node itself, then its right subtree — and collect the values in that order into a list. For a binary search tree, this produces the node values in ascending sorted order.

[4,2,6,1,3,5,7]

• Input: root = [4, 2, 6, 1, 3, 5, 7]
• Output: [1, 2, 3, 4, 5, 6, 7]
• Explanation: Visiting left before root before right on every subtree yields the values in sorted order for this BST.

Intuition

"Inorder" describes where in the output sequence the current node appears — after everything in its left subtree and before everything in its right subtree. A recursive function maps directly to this definition: descend left as far as possible, record each node on the way back up, then descend right. For a BST this ordering produces sorted output, which is why inorder is the default traversal whenever a problem needs values "in order."

Solution — Recursive DFS

Use a nested helper to accumulate values: recurse left, append the current value, then recurse right. An outer result list captures values across all stack frames without needing to merge return values.

1. Create an empty result list and define a recursive dfs helper that takes a single node.
2. If the node is null, return immediately — this handles missing children without special-casing.
3. Recurse into the left child to fully process the left subtree before recording anything.
4. Append the current node's value to the result list.
5. Recurse into the right child.
6. Kick off the traversal with dfs(root) and return the result list.

1class Solution:
2    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
3        result = []
4
5        def dfs(node):
6            if not node:
7                return
8            dfs(node.left)
9            result.append(node.val)  # visit root only after the entire left subtree is done
10            dfs(node.right)
11
12        dfs(root)
13        return result

Time: O(n) — every node is visited exactly once.

Space: O(h) — the call stack holds at most h frames where h is the tree height; O(log n) for a balanced tree, O(n) for a degenerate (fully skewed) tree.

Complexity Summary

Common Mistakes

• Placing the append before the left recursion — writing result.append(node.val) before dfs(node.left) turns inorder into preorder. The mnemonic: "in-order" puts the root in the middle, so the append must come between the two recursive calls.
• Concatenating sublists instead of sharing a result list — writing return dfs(node.left) + [node.val] + dfs(node.right) creates and copies lists at every node, blowing space up to O(n log n) for balanced trees due to repeated allocation.
• Assuming inorder always produces sorted output — this holds only for BSTs. On an arbitrary binary tree the traversal order is deterministic but the values are not sorted; applying this assumption to a non-BST silently produces wrong answers.
• In the iterative version, forgetting to advance to the right child after popping — the most common iterative bug is not setting current = popped_node.right after recording the value, which causes the inner loop to immediately re-push the same left spine and loop forever.
• Skipping the null check — without if not node: return, recursing into a leaf's missing child crashes with an AttributeError in Python or NullPointerException in Java; the null guard must be the very first line of the helper.

Related Problems

• kth-smallest-element-in-a-bst — inorder traversal directly yields BST values in sorted order; the k-th smallest is simply the k-th value visited
• binary-tree-preorder-traversal — identical recursive structure with the append moved before the left recursion
• binary-tree-postorder-traversal — identical recursive structure with the append moved after both recursive calls
• recover-binary-search-tree — uses inorder traversal to detect the two nodes whose values break the expected sorted sequence
• lowest-common-ancestor-of-a-binary-search-tree — exploits the sorted ordering that inorder traversal reveals about a BST