07 — Trees

Neetcode Weeks 6–7a. Trees are the most-asked DS at Google. Almost every tree problem reduces to "pick a traversal, then carry state through it." This doc gets you fluent with traversals and the recursive thinking that powers them.

Table of Contents

1. Tree terminology
2. Binary tree node
3. Traversals — the foundation
4. BFS (level order)
5. DFS recursion patterns
6. Binary search tree (BST)
7. Walked-through problems
8. Tree construction
9. Serialize / deserialize
10. Pitfalls
11. Practice list

---

1. Tree terminology

              1            ← root        depth 0
             / \
            2   3                        depth 1
           / \   \
          4   5   6        ← leaves      depth 2

Term	Meaning
Root	Topmost node, no parent
Leaf	Node with no children
Depth of node	edges from root
Height of node	edges to deepest leaf below
Height of tree	height of root
Subtree	A node and all its descendants
Balanced	Heights of left and right subtrees differ by ≤ 1 (most definitions)
Complete binary tree	All levels filled except possibly last (left-aligned)
Full / strict binary tree	Every node has 0 or 2 children
Perfect binary tree	All levels fully filled — 2^h leaves

A binary tree of height h has at most 2^(h+1) - 1 nodes. So a balanced tree of n nodes has height O(log n). A skewed tree has height O(n).

This is why balance matters — an unbalanced BST degrades all operations to O(n).

---

2. Binary tree node

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

---

3. Traversals — the foundation

There are 4 standard ways to visit every node:

                1
              /   \
             2     3
            / \
           4   5

Traversal	Order
Preorder (root, L, R)	1, 2, 4, 5, 3
Inorder (L, root, R)	4, 2, 5, 1, 3
Postorder (L, R, root)	4, 5, 2, 3, 1
Level-order (BFS)	1, 2, 3, 4, 5

Recursive (clean)

def preorder(root):
    if not root: return
    print(root.val)        # visit
    preorder(root.left)
    preorder(root.right)

def inorder(root):
    if not root: return
    inorder(root.left)
    print(root.val)        # visit between subtrees
    inorder(root.right)

def postorder(root):
    if not root: return
    postorder(root.left)
    postorder(root.right)
    print(root.val)        # visit after both subtrees

Iterative (using a stack)

def preorder_iter(root):
    if not root: return []
    stack = [root]
    out = []
    while stack:
        n = stack.pop()
        out.append(n.val)
        if n.right: stack.append(n.right)    # push right first
        if n.left:  stack.append(n.left)     # so left is processed first
    return out

def inorder_iter(root):
    out = []
    stack = []
    cur = root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        out.append(cur.val)
        cur = cur.right
    return out

Postorder iterative is the trickiest (use two stacks or a "visited" flag — most interviewers accept the recursive version).

When to use which

Goal	Traversal
Copy / serialize tree (root info first)	Preorder
Sort BST in ascending order	Inorder of BST gives sorted sequence
Compute subtree info that depends on children (e.g., height)	Postorder (children first, then combine)
Visit by depth	BFS

Rule of thumb: if your computation needs info from children before processing the node, use postorder. That's most "compute X for each subtree" problems.

---

4. BFS (level order)

Trigger: "level order," "right-side view," "minimum depth," "shortest path in unweighted tree/graph."

Use a queue. Process all current-level nodes before next level.

from collections import deque

def level_order(root):
    if not root: return []
    q = deque([root])
    res = []
    while q:
        level_size = len(q)             # snapshot — fixed for this level
        level = []
        for _ in range(level_size):
            n = q.popleft()
            level.append(n.val)
            if n.left:  q.append(n.left)
            if n.right: q.append(n.right)
        res.append(level)
    return res

The level_size = len(q) snapshot is the trick — at the start of an iteration of the outer loop, the queue contains exactly the current level. We pop that many, leaving the next level.

Right Side View

Show only the rightmost node of each level.

def right_side_view(root):
    if not root: return []
    q = deque([root])
    res = []
    while q:
        level_size = len(q)
        for i in range(level_size):
            n = q.popleft()
            if i == level_size - 1:      # last in this level
                res.append(n.val)
            if n.left:  q.append(n.left)
            if n.right: q.append(n.right)
    return res

---

5. DFS recursion patterns

The shape of a tree-recursion solution is one of three types:

Type 1: "Compute a value for each subtree" (postorder reduction)

def height(root):
    if not root: return 0
    left = height(root.left)
    right = height(root.right)
    return 1 + max(left, right)

The pattern: recurse on both subtrees, combine results, return. The combine is where the logic lives.

Type 2: "Carry state down" (preorder, with parameter)

def has_path_sum(root, target):
    if not root: return False
    target -= root.val
    if not root.left and not root.right:
        return target == 0
    return has_path_sum(root.left, target) or has_path_sum(root.right, target)

The state (target here) flows top-down via the parameter. Each call modifies and passes on.

Type 3: "Two answers — local and global" (using nonlocal / class member)

For problems like Diameter, Maximum Path Sum, you need:

• A return value describing what's usable as a sub-result for parent.
• A global describing the answer across all subtrees.

def diameter(root):
    diameter_val = [0]                       # using list as a 1-element container for closure
    
    def height(node):
        if not node: return 0
        l = height(node.left)
        r = height(node.right)
        diameter_val[0] = max(diameter_val[0], l + r)
        return 1 + max(l, r)
    
    height(root)
    return diameter_val[0]

Key idea: height returns the height (usable by parent), but along the way records the diameter through the current node. The diameter through a node v is height(v.left) + height(v.right).

This pattern is the secret to solving:

• Diameter of Binary Tree
• Binary Tree Maximum Path Sum
• Longest Univalue Path
• Find Duplicate Subtrees

The trick: what does each node need to return up vs record globally?

---

6. Binary search tree (BST)

A binary tree where every node satisfies: left.val < node.val < right.val (typically), recursively.

            8
          /   \
         3     10
        / \      \
       1   6      14
          / \    /
         4   7  13

BST invariant gives us ordering

Inorder traversal of a BST visits values in sorted order.

def inorder(root):
    if not root: return
    inorder(root.left)
    print(root.val)
    inorder(root.right)

For the tree above: 1, 3, 4, 6, 7, 8, 10, 13, 14.

Operations

Op	Avg (balanced)	Worst (skewed)
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

Search

def search(root, target):
    while root:
        if root.val == target: return root
        if target < root.val: root = root.left
        else: root = root.right
    return None

Insert

def insert(root, val):
    if not root: return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

Delete (the only tricky op)

Three cases:

1. Leaf → remove.
2. One child → replace with child.
3. Two children → replace with in-order successor (smallest in right subtree), then delete that successor recursively.

def delete(root, key):
    if not root: return None
    if key < root.val:
        root.left = delete(root.left, key)
    elif key > root.val:
        root.right = delete(root.right, key)
    else:                                       # found
        if not root.left:  return root.right
        if not root.right: return root.left
        # two children
        succ = root.right
        while succ.left:
            succ = succ.left
        root.val = succ.val
        root.right = delete(root.right, succ.val)
    return root

Validate BST

Return whether a tree is a valid BST.

Wrong approach: check node.left.val < node.val < node.right.val for each node — fails because all descendants on left must be less, not just the immediate child.

        5
       / \
      3   8
         / \
        2   9     ← 2 is in 8's left, 2 < 8, but 2 < 5 violated!

Correct approach: pass in (low, high) bounds.

def is_valid_bst(root, low=float('-inf'), high=float('inf')):
    if not root: return True
    if not (low < root.val < high): return False
    return (is_valid_bst(root.left, low, root.val) and
            is_valid_bst(root.right, root.val, high))

Lowest Common Ancestor (BST version, easy)

In a BST, the LCA of p and q is the first node where the values split:

def lca_bst(root, p, q):
    while root:
        if p.val < root.val and q.val < root.val:
            root = root.left
        elif p.val > root.val and q.val > root.val:
            root = root.right
        else:
            return root                          # p and q on different sides (or equal to root)

For LCA on a general binary tree, see §7.

Kth Smallest in BST

Inorder traversal yields sorted; stop after k.

def kth_smallest(root, k):
    stack = []
    cur = root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        k -= 1
        if k == 0: return cur.val
        cur = cur.right

---

7. Walked-through problems

Maximum Depth (Easy)

def max_depth(root):
    if not root: return 0
    return 1 + max(max_depth(root.left), max_depth(root.right))

Same Tree (Easy)

def is_same(p, q):
    if not p and not q: return True
    if not p or not q: return False
    if p.val != q.val: return False
    return is_same(p.left, q.left) and is_same(p.right, q.right)

Subtree of Another Tree (Easy)

def is_subtree(root, sub):
    if not root: return False
    if is_same(root, sub): return True
    return is_subtree(root.left, sub) or is_subtree(root.right, sub)

Complexity: O(n × m) worst case.

Invert Binary Tree (Easy)

def invert(root):
    if not root: return None
    root.left, root.right = invert(root.right), invert(root.left)
    return root

Balanced Binary Tree (Easy)

Height-difference of every subtree is ≤ 1.

def is_balanced(root):
    def check(node):
        if not node: return 0
        l = check(node.left)
        if l == -1: return -1
        r = check(node.right)
        if r == -1: return -1
        if abs(l - r) > 1: return -1
        return 1 + max(l, r)
    return check(root) != -1

Encoding "unbalanced" as -1 lets us short-circuit. O(n) instead of O(n²).

Binary Tree Maximum Path Sum (Hard)

Find the path (any direction, including up-and-back-down) with maximum sum.

def max_path_sum(root):
    best = [float('-inf')]
    
    def gain(node):
        if not node: return 0
        l = max(gain(node.left), 0)              # take left only if positive
        r = max(gain(node.right), 0)
        best[0] = max(best[0], node.val + l + r) # path through node
        return node.val + max(l, r)              # gain to parent: only one side
    
    gain(root)
    return best[0]

Classic Type 3 (local return + global tracking) pattern. The path through a node can use both children, but the gain up to a parent must use only one side (or the path wouldn't be a path).

Lowest Common Ancestor — General Binary Tree (Medium)

def lca(root, p, q):
    if not root or root == p or root == q:
        return root
    left = lca(root.left, p, q)
    right = lca(root.right, p, q)
    if left and right: return root           # p and q split here
    return left or right                     # both on one side, or none found

Beautiful recursive pattern: each subtree call returns "where p or q (or LCA) was found in this subtree, if anywhere." If both sides return non-null, current node is the LCA.

---

8. Tree construction

Build Binary Tree from Preorder + Inorder (Medium)

preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]. Build the unique tree.

Idea: preorder's first element is root. Find it in inorder → splits inorder into left/right subtrees → recurse.

def build_tree(preorder, inorder):
    if not preorder: return None
    root_val = preorder[0]
    idx = inorder.index(root_val)            # split point
    root = TreeNode(root_val)
    root.left = build_tree(preorder[1:idx+1], inorder[:idx])
    root.right = build_tree(preorder[idx+1:], inorder[idx+1:])
    return root

O(n²) due to inorder.index(). To make it O(n), pre-compute a hashmap value → inorder index, then pass index ranges instead of slicing.

def build_tree(preorder, inorder):
    inorder_idx = {v: i for i, v in enumerate(inorder)}
    pre_iter = iter(preorder)
    
    def helper(lo, hi):
        if lo > hi: return None
        val = next(pre_iter)
        root = TreeNode(val)
        i = inorder_idx[val]
        root.left = helper(lo, i - 1)
        root.right = helper(i + 1, hi)
        return root
    
    return helper(0, len(inorder) - 1)

pre_iter walks preorder once globally — root choices come in the right order.

---

9. Serialize / deserialize

Convert a tree to a string, then back. Useful for IPC or storing trees on disk.

Approach: preorder with explicit nulls.

def serialize(root):
    out = []
    def dfs(n):
        if not n:
            out.append('#')
            return
        out.append(str(n.val))
        dfs(n.left)
        dfs(n.right)
    dfs(root)
    return ','.join(out)

def deserialize(s):
    vals = iter(s.split(','))
    def dfs():
        v = next(vals)
        if v == '#': return None
        n = TreeNode(int(v))
        n.left = dfs()
        n.right = dfs()
        return n
    return dfs()

Why preorder? Reading values in preorder lets us reconstruct uniquely if we mark nulls explicitly.

Variant: BFS-based (LeetCode-style)

[1,2,3,null,null,4,5]

This is also fine. Choose one and be consistent.

---

10. Pitfalls

Off-by-one in traversal

For inorder iterative: cur = cur.right after popping and printing — easy to forget.

Mutating tree during traversal

Don't write to node.left while iterating its descendants. If you must, do it in a postorder (children done before parent).

Confusing height vs depth

• Depth: from root downward (root has depth 0).
• Height: from leaf upward (leaf has height 0).

Some problems use "1-indexed" depth/height. Read carefully.

Forgetting balance assumption

"BST search is O(log n)" assumes balance. In raw BSTs it's O(h). Self-balancing variants (AVL, Red-Black) maintain O(log n). LeetCode usually assumes the input could be skewed; state your bounds correctly.

LCA on general tree vs BST

LCA on BST uses ordering (O(log n) average). LCA on general tree uses recursive split detection (O(n)). Don't confuse them.

Forgetting to return in recursion

def invert(node):
    if not node: return None
    node.left, node.right = invert(node.right), invert(node.left)
    # forgetting `return node` here

The function compiles but every call returns None, breaking subsequent references.

Counting both directions in path sum

In Binary Tree Maximum Path Sum, the path through a node can go down both sides — but the gain returned to a parent must pick only one side.

---

11. Practice list

Easy/Medium

#	Problem	Pattern	Difficulty
226	Invert Binary Tree	DFS	Easy
104	Maximum Depth	DFS postorder	Easy
543	Diameter	DFS + global	Easy
110	Balanced Binary Tree	DFS short-circuit	Easy
100	Same Tree	Parallel recursion	Easy
572	Subtree of Another Tree	DFS + same-tree	Easy
235	LCA of BST	BST split	Medium
102	Level Order Traversal	BFS	Medium
199	Right Side View	BFS last-of-level	Medium
1448	Count Good Nodes	DFS with carry-down	Medium
98	Validate BST	Bounds	Medium
230	Kth Smallest in BST	Iterative inorder	Medium
105	Build Tree from Preorder/Inorder	Recursive with map	Medium
236	LCA of Binary Tree	Recursive split	Medium

Hard

#	Problem	Pattern	Difficulty
124	Binary Tree Maximum Path Sum	Local + global	Hard
297	Serialize and Deserialize Binary Tree	Preorder w/ nulls	Hard

---

TL;DR ✅

• Trees recurse naturally. Most solutions are postorder or BFS variants.
• Inorder of a BST is sorted — use this to validate, find kth smallest, etc.
• Type 3 pattern (return-value + global) solves diameter, max-path-sum, and similar problems.
• BFS with level_size = len(q) processes one level at a time — used for level-order, right-side view, minimum depth.
• LCA on BST uses split-point property; LCA on general tree uses recursive return.
• Build from preorder + inorder uses split index from inorder; cache it for O(n).
• Serialize/deserialize: preorder with # for null, then preorder reconstruct.

Next: 08-tries.md.

External resources

• NeetCode Trees playlist: https://www.youtube.com/playlist?list=PLot-Xpze53lcvx_tjrr_m2lgD2NsRHlNO
• VisuAlgo BST: https://visualgo.net/en/bst
• Tree traversals (animated): https://www.cs.usfca.edu/~galles/visualization/BST.html