LeetCode #94 Easy

Binary Tree Inorder Traversal

Given the root of a binary tree, return the inorder traversal of its node values: left subtree, then the node, then the right subtree.

binary treedfsrecursion

Open on LeetCode ↗

02

Intuition

Inorder is just three lines that call themselves: finish everything on the left, record the node, then do the right. The call stack remembers where you came from — on a BST this visits values in sorted order.

How to spot this pattern

Left, node, right. On a BST this order emits values sorted, which is why inorder shows up in so many BST problems — validation, k-th smallest, converting to a sorted list. The traversal order is the algorithm in those cases.

03

Approach

1

Trust the recursive definition

Inorder of a tree = inorder of the left subtree + this node + inorder of the right subtree. That sentence is the algorithm — write a helper that recurses left, appends node.val, then recurses right. An empty child is the base case: return without doing anything.

2

The call stack does the bookkeeping

No manual tracking is needed: when the left recursion returns, execution resumes exactly at the append. That's why the traversal 'climbs back up' for free. Depth of recursion equals the height of the tree.

3

Iterative version, if asked

Interviewers often follow up with 'now without recursion'. Simulate the stack yourself: push nodes while running left, pop to visit, then switch to the popped node's right child. Same order, explicit stack.

04

Solution & live demo

▶1class Solution:
▶2    def inorderTraversal(self, root):
▶3        res = []
▶4        def dfs(node):
▶5            if not node:
▶6                return
▶7            dfs(node.left)
▶8            res.append(node.val)
▶9            dfs(node.right)
▶10        dfs(root)
▶11        return res

05

Common pitfalls

Appending before recursing left

✗ Wrong

res.append(node.val)
dfs(node.left)
dfs(node.right)

✓ Right

dfs(node.left)
res.append(node.val)
dfs(node.right)

That's preorder. The three traversals differ only in where the visit sits relative to the two recursive calls, so a misplaced line silently produces a valid-looking but wrong order.

Returning a new list from each call and concatenating carelessly

✗ Wrong

return dfs(node.left) + node.val + dfs(node.right)

✓ Right

res = []
def dfs(node): ...

node.val is an int, not a list, so the concatenation throws — and even written correctly as [node.val], allocating a fresh list at every node is O(n²) in the worst case. A shared accumulator appends in O(1).

Missing the null base case

✗ Wrong

def dfs(node):
    dfs(node.left)

✓ Right

def dfs(node):
    if not node:
        return

Leaves have None children, so the recursion must stop there. Without the guard the first leaf dereferences None and throws.

06

Edge cases

Empty tree

The base case fires immediately — return the empty list.

Skewed tree (all left or all right children)

Recursion depth reaches n, so the traversal degenerates to a simple walk; output is still correct.

Single node

Left recursion returns instantly, node is visited, right returns — result is [root.val].

07

Complexity

Time

O(n)

Space

O(h)

Every node visited once; the recursion stack holds one path — h is the tree height.