Trees

When to Use

• Hierarchical data, parent-child relationships
• Path, depth, LCA, validation problems
• DFS → path/property problems, BST operations
• BFS → level-by-level, shortest path to leaf, right/left view

Signal phrases: "level order", "zigzag", "right side view", "path sum", "LCA", "validate BST", "diameter", "serialize", "kth smallest", "flatten", "top view"

---

Pattern 1 — BFS (Level Order)

Always uses a Queue. "Level Size Trick" = snapshot len(queue) at loop start to know how many nodes are in the current level.

from collections import deque

# Standard level order
def levelOrder(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)    # snapshot current level size
        level = []
        for _ in range(level_size):
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level)
    return result

# LC 103 — Zigzag Level Order
def zigzagLevelOrder(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    left_to_right = True
    while queue:
        level = []
        for _ in range(len(queue)):
            node = queue.popleft()
            level.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
        result.append(level if left_to_right else level[::-1])
        left_to_right = not left_to_right
    return result

# LC 199 — Binary Tree Right Side View
def rightSideView(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        for i in range(len(queue)):
            node = queue.popleft()
            if i == len(queue):   # last node of current level
                result.append(node.val)
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
    return result

# LC 111 — Minimum Depth (BFS preferred — first leaf found = min depth)
def minDepth(root):
    if not root:
        return 0
    queue = deque([(root, 1)])
    while queue:
        node, depth = queue.popleft()
        if not node.left and not node.right:
            return depth    # first leaf = guaranteed minimum
        if node.left:  queue.append((node.left, depth + 1))
        if node.right: queue.append((node.right, depth + 1))

BFS vs DFS: BFS for level questions, averages, min depth. DFS would waste time going deep first.

---

Pattern 2 — DFS (Pre / In / Post Order)

# DFS template — where you place logic determines order
def dfs(node):
    if not node:
        return

    # PRE-ORDER spot (Root → Left → Right)
    # Use: clone tree, serialize, count nodes, path sum down

    dfs(node.left)

    # IN-ORDER spot (Left → Root → Right)
    # Use: BST in sorted order, validate BST, Kth smallest

    dfs(node.right)

    # POST-ORDER spot (Left → Right → Root)
    # Use: delete tree, height/diameter, bottom-up calculations

# LC 112 — Path Sum (root to leaf)
def hasPathSum(root, target):
    if not root:
        return False
    if not root.left and not root.right:    # leaf
        return target == root.val
    return (hasPathSum(root.left, target - root.val) or
            hasPathSum(root.right, target - root.val))

# LC 230 — Kth Smallest in BST (in-order = sorted, decrement counter)
def kthSmallest(root, k):
    result = []
    def inorder(node):
        if not node or len(result) == k:
            return
        inorder(node.left)
        result.append(node.val)
        inorder(node.right)
    inorder(root)
    return result[k - 1]

# LC 114 — Flatten Binary Tree to Linked List (reverse pre-order)
def flatten(root):
    prev = [None]
    def dfs(node):
        if not node:
            return
        dfs(node.right)      # process right first (reverse pre-order)
        dfs(node.left)
        node.right = prev[0]
        node.left = None
        prev[0] = node
    dfs(root)

---

Pattern 3 — Bottom-Up DFS (Post-Order Return)

"To know the answer for the current node, I first need answers from left and right children." Information flows UP from leaves to root.

# Bottom-Up template
def solve(node):
    if not node:
        return base_value   # neutral: 0 for height, None for LCA

    left_result  = solve(node.left)    # get answer from left subtree
    right_result = solve(node.right)   # get answer from right subtree

    # Compute current node's answer using children's answers
    current_answer = combine(left_result, right_result, node)

    return current_answer   # pass UP to parent

# LC 104 — Max Depth
def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

# LC 543 — Diameter of Binary Tree (Global Variable Trick)
def diameterOfBinaryTree(root):
    diameter = [0]

    def height(node):
        if not node:
            return 0
        left_h  = height(node.left)
        right_h = height(node.right)
        diameter[0] = max(diameter[0], left_h + right_h)   # update global answer
        return 1 + max(left_h, right_h)   # return HEIGHT to parent (not diameter!)

    height(root)
    return diameter[0]

# LC 124 — Binary Tree Maximum Path Sum
def maxPathSum(root):
    res = [root.val]

    def dfs(node):
        if not node:
            return 0
        left  = max(dfs(node.left), 0)     # ignore negative branches
        right = max(dfs(node.right), 0)
        res[0] = max(res[0], node.val + left + right)   # full path through node
        return node.val + max(left, right)  # single branch returned to parent

    dfs(root)
    return res[0]

# LC 236 — LCA of Binary Tree
def lowestCommonAncestor(root, p, q):
    if not root or root == p or root == q:
        return root
    left  = lowestCommonAncestor(root.left, p, q)
    right = lowestCommonAncestor(root.right, p, q)
    if left and right:
        return root     # p in one subtree, q in other → current node is LCA
    return left or right

Global Variable Trick: Return value to parent = what parent needs (height). Update global = what problem asks for (diameter). These are often DIFFERENT.

---

Pattern 4 — Top-Down DFS (Accumulator / Pass Down)

Pass a value DOWN from parent to children. Carry an accumulator (running sum, current path list, prefix sum map).

# LC 257 — Binary Tree Paths (collect all root-to-leaf paths)
def binaryTreePaths(root):
    result = []
    def dfs(node, path):
        if not node:
            return
        path.append(str(node.val))
        if not node.left and not node.right:
            result.append('->'.join(path))
        dfs(node.left, path)
        dfs(node.right, path)
        path.pop()    # backtrack
    dfs(root, [])
    return result

# LC 437 — Path Sum III (count paths summing to target, any node start)
def pathSum(root, targetSum):
    from collections import defaultdict
    prefix_count = defaultdict(int)
    prefix_count[0] = 1

    def dfs(node, current_sum):
        if not node:
            return 0
        current_sum += node.val
        count = prefix_count[current_sum - targetSum]   # paths ending here
        prefix_count[current_sum] += 1
        count += dfs(node.left, current_sum) + dfs(node.right, current_sum)
        prefix_count[current_sum] -= 1   # backtrack
        return count

    return dfs(root, 0)

Top-Down vs Bottom-Up: Top-Down passes accumulator DOWN (path sum, running total). Bottom-Up collects answers from children and sends UP (height, LCA).

---

Pattern 5 — Tree Structure & Construction

# LC 226 — Invert Binary Tree
def invertTree(root):
    if not root:
        return None
    root.left, root.right = invertTree(root.right), invertTree(root.left)
    return root

# LC 105 — Construct from Preorder + Inorder
def buildTree(preorder, inorder):
    if not inorder:
        return None
    root_val = preorder[0]
    root = TreeNode(root_val)
    mid = inorder.index(root_val)   # root splits inorder into left/right
    root.left  = buildTree(preorder[1:mid+1], inorder[:mid])
    root.right = buildTree(preorder[mid+1:], inorder[mid+1:])
    return root

# LC 297 — Serialize and Deserialize Binary Tree (pre-order)
class Codec:
    def serialize(self, root):
        res = []
        def dfs(node):
            if not node:
                res.append('N')
                return
            res.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        return ','.join(res)

    def deserialize(self, data):
        vals = iter(data.split(','))
        def dfs():
            val = next(vals)
            if val == 'N':
                return None
            node = TreeNode(int(val))
            node.left  = dfs()
            node.right = dfs()
            return node
        return dfs()

---

Pattern 6 — Tree View Patterns

from collections import deque, defaultdict

# LC 199 — Right Side View (BFS: take last element of each level)
def rightSideView(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        for i in range(level_size):
            node = queue.popleft()
            if i == level_size - 1:
                result.append(node.val)    # last node of level = visible from right
            if node.left:  queue.append(node.left)
            if node.right: queue.append(node.right)
    return result

# Top / Bottom View — horizontal distance (HD) map
# Going left: HD -= 1. Going right: HD += 1.
# Top view: first node seen at each HD. Bottom view: last node at each HD.
def topView(root):
    if not root:
        return []
    hd_map = {}      # horizontal_distance → first node value
    queue = deque([(root, 0)])    # (node, horizontal_distance)
    while queue:
        node, hd = queue.popleft()
        if hd not in hd_map:
            hd_map[hd] = node.val   # first = top view
        if node.left:  queue.append((node.left,  hd - 1))
        if node.right: queue.append((node.right, hd + 1))
    return [hd_map[k] for k in sorted(hd_map)]

---

Pattern 7 — BST-Specific Patterns

These only apply when tree is sorted (left < node < right).

# LC 98 — Validate BST (pass min/max bounds down)
def isValidBST(root, min_val=float('-inf'), max_val=float('inf')):
    if not root:
        return True
    if not (min_val < root.val < max_val):
        return False
    return (isValidBST(root.left,  min_val, root.val) and
            isValidBST(root.right, root.val, max_val))

# LC 230 — Kth Smallest in BST (in-order = ascending sorted)
def kthSmallest(root, k):
    count = [0]
    result = [None]
    def inorder(node):
        if not node or result[0] is not None:
            return
        inorder(node.left)
        count[0] += 1
        if count[0] == k:
            result[0] = node.val
            return
        inorder(node.right)
    inorder(root)
    return result[0]

# BST Range Search (prune branches outside [low, high])
def rangeSumBST(root, low, high):
    if not root:
        return 0
    total = 0
    if low <= root.val <= high:
        total += root.val
    if root.val > low:    # left subtree may have values in range
        total += rangeSumBST(root.left, low, high)
    if root.val < high:   # right subtree may have values in range
        total += rangeSumBST(root.right, low, high)
    return total

# LC 700 — Search BST
def searchBST(root, val):
    if not root or root.val == val:
        return root
    return searchBST(root.left if val < root.val else root.right, val)

BST in-order = sorted. Any "Kth smallest/largest" or "sorted range" problem → think in-order DFS + counter.

---

Pattern Decision Map

---

Problems

---

Related

• [[DSA/DSA Techniques for Interviews/11. Graphs]] — trees are a special case of DAGs
• [[DSA/DSA Techniques for Interviews/10. Backtracking]] — path collection uses backtracking
• [[DSA/Data Structures/Trees & BST]] — data structure internals
• [[DSA/DSA Topics]] — index