Topic 7: Trees

Canonical Questions #

Basic Traversals (DFS & BFS) #

• Recursive and iterative traversals: preorder, inorder, postorder, level order

Problems #

1. Preorder Traversal (144)

   Classic stuff

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

   # M1: recursive # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]: def traverse(root): if not root: return [] res = [] res.append(root.val) if root.left: res.extend(traverse(root.left)) if root.right: res.extend(traverse(root.right)) return res return traverse(root) # here's the iterative version: def iterative_preorder(root): if not root: return stack = [root] while stack: node = stack.pop() print(node.val) # Preorder position: process node before children # Push right first so left is processed first from the stack if node.right: stack.append(node.right) if node.left: stack.append(node.left)

   Code Snippet 1: Preorder Traversal (144)
   Pattern Extraction

   Core Insight: Visit root, then left subtree, then right subtree. Iteratively: stack-based, push right child first (so left is processed first via LIFO). Pattern Name: DFS Preorder (Root-Left-Right) Canonical Section: Trees > Traversal Recognition Signals:

   • “Preorder traversal” or “root-left-right”
   • Need to process root before subtrees

   Anti-Signals:

   • Need sorted output from BST – inorder
   • Need to process children before parent – postorder

   Decision Point: Preorder = process before recursing. Inorder = process between left and right. Postorder = process after both.

   Pitfalls and Misconceptions

   1. Trap: In iterative version, pushing left child before right onto the stack. Why: Stack is LIFO. Left should be processed first, so push right first. Correction: stack.push(right); stack.push(left).
   Problem Mutations

   1. What if you needed Morris traversal (\(O(1)\) space)? (stress-tests: \(O(h)\) stack space) Thread the tree using right pointers of in-order predecessors. \(O(n)\) time, \(O(1)\) space.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Preorder Traversal.
   

2. Inorder Traversal (94)

   The iterative version just needs to left-bias as much as possible.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

   # M1: iterative solution (a little more complex) # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] stack = [] res = [] curr = root while stack or curr: while curr: stack.append(curr) curr = curr.left curr = stack.pop() res.append(curr.val) curr = curr.right return res # M2: recursive solution: class Solution: def recursive_inorderTraversal(self, root: Optional[TreeNode]) -> List[int]: def traverse(root): res = [] if not root: return [] return traverse(root.left) + [root.val] + traverse(root.right) return traverse(root)

   Code Snippet 2: Inorder Traversal (94)
   Pattern Extraction

   Core Insight: Process left subtree, visit root, then right subtree. Iteratively: push all left children, pop and visit, move to right child. Pattern Name: DFS Inorder (Left-Root-Right) Canonical Section: Trees > Traversal Recognition Signals:

   • “Inorder traversal” or need sorted output from BST
   • BST inorder = sorted order

   Anti-Signals:

   • Need root first – preorder
   • Tree is not a BST – inorder doesn’t give sorted output

   Decision Point: Inorder is the canonical BST traversal. For general trees, it’s just one of three DFS orders.

   Pitfalls and Misconceptions

   1. Trap: In iterative version, not pushing ALL left children before visiting. Why: Must fully descend to the leftmost node before visiting anything. Correction: while curr: stack.push(curr); curr = curr.left. Then pop, visit, move right.
   Problem Mutations

   1. What if you needed the $k$-th element? (stress-tests: full traversal) Early termination after \(k\) visits. Connects to LC 230.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Inorder Traversal.
   

3. Postorder Traversal (145)

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

   class Solution: def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]: def traverse(root): """ Traverse helper function is easy to implement, just controlling the order of operations gives us the different types of traversals. """ res = [] if not root: return [] return traverse(root.left) + traverse(root.right) + [root.val] return traverse(root) def iterative_postorder(root): if not root: return stack = [root] result = [] while stack: node = stack.pop() # we gather results in reversed order (parent > left > right) so that we can eventually reverse it and get (right -> left -> parent), which is the post-order. result.append(node.val) if node.left: stack.append(node.left) if node.right: stack.append(node.right) # Reverse to get Left-Right-Root order for val in reversed(result): print(val)

   Code Snippet 3: Postorder Traversal (145)
   Pattern Extraction

   Core Insight: Process left subtree, right subtree, then root. Iteratively: tricky because root is visited AFTER children. Use modified preorder (root-right-left) and reverse the result. Pattern Name: DFS Postorder (Left-Right-Root) Canonical Section: Trees > Traversal Recognition Signals:

   • “Postorder traversal” or need to process children before parent
   • Useful for bottom-up computation (heights, sizes, deletion)

   Anti-Signals:

   • Need to process root first – preorder

   Decision Point: Postorder iterative is hardest of the three. The reverse-of-modified-preorder trick simplifies it enormously.

   Pitfalls and Misconceptions

   1. Trap: Trying to implement iterative postorder directly without the reversal trick. Why: Directly tracking “has this node’s right subtree been processed?” requires a prev pointer or flag, adding complexity. Correction: Modified preorder (root-right-left) with result reversal. Or use a prev pointer to detect right subtree completion.
   Problem Mutations

   1. What if the tree were N-ary? (stress-tests: binary) Push children in reverse order. Otherwise same logic.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Postorder Traversal.
   

4. Level Order Traversal (102)

   Here, we directly build the final list, when there’s a new level we enter, we init the [] at the end too. Here we avoid building intermediate lists and build things directly!

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: if not root: return [] levels = [] queue = deque([(root, 0)]) # Start at level 0 while queue: node, level = queue.popleft() if len(levels) == level: levels.append([]) levels[level].append(node.val) if node.left: queue.append((node.left, level + 1)) if node.right: queue.append((node.right, level + 1)) return levels

   Code Snippet 4: Level Order Traversal (102)

   Here’s a state-threaded recursive dfs version:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   class Solution: def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]: levels = [] def dfs(node, level): if not node: return if len(levels) == level: levels.append([]) levels[level].append(node.val) dfs(node.left, level + 1) dfs(node.right, level + 1) if root: dfs(root, 0) return levels

   Code Snippet 5: Level Order Traversal (102)
   Pattern Extraction

   Core Insight: BFS with a queue, processing all nodes at the same depth before moving to the next level. Track level boundaries by processing len(queue) nodes per iteration. Pattern Name: BFS Level-by-Level Processing Canonical Section: Trees > Traversal Recognition Signals:

   • “Level order” or “breadth-first” traversal
   • Need to group nodes by depth
   • Queue-based processing

   Anti-Signals:

   • Need preorder/inorder/postorder – use DFS (recursive or stack-based)
   • Need zigzag order – BFS with alternating reversal. Connects to LC 103

   Decision Point: Level-by-level = BFS with level size tracking. Depth-first variants = DFS.

   Pitfalls and Misconceptions

   1. Trap: Not tracking level boundaries, producing a flat list instead of a list of levels. Why: Without processing exactly len(queue) nodes per level, you can’t group by depth. Correction: level_size = len(queue); for _ in range(level_size): ....
   2. Trap: Appending None children to the queue. Why: Null children produce errors when you try to access their values/children. Correction: Only enqueue non-None children: if node.left: queue.append(node.left).
   Problem Mutations

   1. What if you needed right-side view? (stress-tests: full level output) Last node in each level during BFS. Connects to LC 199.
   2. What if you needed zigzag order? (stress-tests: left-to-right only) Alternate the direction of reading each level. Connects to LC 103.
   3. What if the tree were an N-ary tree instead of binary? (stress-tests: binary tree) Iterate over node.children instead of node.left, node.right. Same BFS structure.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Level Order Traversal generated via batch canonical enrichment pass.
   

5. Binary Tree Right Side View (199)

   Key idea here is that we can just BFS and take last or do a right-biased DFS:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59

   # M1: BFS, TAKE LAST ELEMENT from collections import deque # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] queue = deque([root]) res = [] while queue: last = queue[-1] res.append(last.val) for _ in range(len(queue)): node = queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) return res # M2: ITERATIVE RIGHT-BIASED DFS class Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] res = [] stack = [(root, 0)] # (node, depth) while stack: node, depth = stack.pop() if node: if depth == len(res): res.append(node.val) # Push left first so right is processed first ==> right-bias stack.append((node.left, depth + 1)) stack.append((node.right, depth + 1)) return res # M3: RECURSIVE RIGHT BIASED DFS: class Solution: def rightSideView(self, root: Optional[TreeNode]) -> List[int]: res = [] def dfs(node, depth): if not node: return if depth == len(res): res.append(node.val) dfs(node.right, depth + 1) dfs(node.left, depth + 1) dfs(root, 0) return res

   Code Snippet 6: Binary Tree Right Side View (199)
   Pattern Extraction

   Core Insight: BFS level-by-level; the last node in each level is visible from the right side. Or: DFS with right-first traversal, collecting the first node seen at each new depth. Pattern Name: BFS Last-in-Level / DFS Right-First by Depth Canonical Section: Trees > Traversal Recognition Signals:

   • “Nodes visible from the right side” = last node per level
   • BFS with level-by-level processing

   Anti-Signals:

   • Left side view – first node per level (or DFS left-first)
   • Need all boundary nodes – more complex traversal

   Decision Point: Right side = last in BFS level OR first in right-first DFS. Either approach is \(O(n)\).

   Pitfalls and Misconceptions

   1. Trap: Using left-first DFS and tracking the last node per depth. Why: Works but requires visiting all nodes. Right-first DFS can short-circuit. Correction: DFS visiting right child first. Track the first node seen at each new depth level.
   Problem Mutations

   1. What if you needed the left side view? (stress-tests: right vs left) First node per BFS level, or left-first DFS.
   2. What if the tree were N-ary? (stress-tests: binary) Last child is the “rightmost.” BFS approach is identical.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Binary Tree Right Side View.
   

Depth, Height, & Diameter Computation #

• Compute tree statistics such as max depth, height, or tree diameter using DFS

Problems #

1. Maximum Depth (104)

   Just a classic level-based traversal, we can choose either BFS or DFS here (just augment the tuple in the stack to keep depth info), I prefer BFS.

   In these tree-statistics as usual, it’s a matter of augmenting the tree nodes / using tuples to keep intermediate information that would help us.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

   from collections import deque class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: if not root: return 0 queue = deque([root]) depth = 0 while queue: # for all parents (each level), find their children: for _ in range(len(queue)): node = queue.popleft() if node.left: queue.append(node.left) if node.right: queue.append(node.right) depth += 1 return depth

   Code Snippet 7: Maximum Depth (104) – iterative bfs solution

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: if not root: return 0 stack = [(root, 1)] max_depth = 0 while stack: node, depth = stack.pop() max_depth = max(max_depth, depth) if node.left: stack.append((node.left, depth + 1)) if node.right: stack.append((node.right, depth + 1)) return max_depth

   Code Snippet 8: Maximum Depth (104) – iterative dfs solution
   Pattern Extraction

   Core Insight: The depth of a tree is 1 + max(depth of left subtree, depth of right subtree). Base case: null node has depth 0. Pattern Name: Recursive Tree Height (Post-Order Aggregation) Canonical Section: Trees > Recursive Measure Properties Recognition Signals:

   • Tree property that decomposes into a function of left and right subtree properties
   • Bottom-up computation (need children’s answers before computing parent’s)
   • Base case at null nodes

   Anti-Signals:

   • Need the path from root to deepest node, not just the depth – track path during recursion
   • Need the depth of a SPECIFIC node – traverse to that node, not full tree

   Decision Point: Any tree property expressible as f(left_result, right_result) is a post-order aggregation. Height, diameter, balance status, and subtree sum all follow this pattern.

   Pitfalls and Misconceptions

   1. Trap: Returning 1 for null nodes instead of 0. Why: Null nodes (leaf’s children) have depth 0, not 1. A single-node tree should have depth 1: 1 + max(0, 0) = 1. Correction: if not node: return 0.
   2. Trap: Confusing height (edges from root to deepest leaf) with depth (edges from root to a specific node). Why: Some definitions use “height” and “depth” interchangeably; others distinguish them. LC 104 counts nodes on the longest path, which is equivalent to height + 1. Correction: Clarify the definition in context: LC 104 counts nodes, not edges.
   Problem Mutations

   1. What if you needed the minimum depth instead of maximum? (stress-tests: max vs min) Base case changes: a null child of a node WITH a non-null sibling should NOT contribute (don’t take min with 0 for nodes that have one child). Connects to LC 111 Minimum Depth.
   2. What if you needed the diameter (longest path between any two nodes)? (stress-tests: root-to-leaf vs any-to-any) At each node, diameter = left_height + right_height. Track global max. Connects to LC 543 Diameter of Binary Tree.
   3. What if you needed to check if the tree is balanced? (stress-tests: measurement vs property) At each node, check abs(left_height - right_height) < 1= AND both subtrees are balanced. Connects to LC 110 Balanced Binary Tree.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Maximum Depth of Binary Tree generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

2. Diameter of Binary Tree (543) We have to know the children’s heights before we can compute a node’s diameter, so it’s a post-order processing that we’re doing (children first then parent). The stack can be explicit (iterative DFS) or implicit (recursive call stack).

   For the recursive function, I think it’s cleaner

   For the iterative DFS version, we store the heights indexed by the node object directly so that we can compute when we need that node.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57

   # M1: RECURSIVE SOLUTION: class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: max_diameter = 0 # returns the max height for that node def traverse(root: Optional[TreeNode]): nonlocal max_diameter if root is None: return 0 # max height left max_left = traverse(root.left) # max height right max_right = traverse(root.right) combined = max_left + max_right # compare with the global accumulator max_diameter = max(max_diameter, combined) # returns the max height of either choices with an extra edge here return max(max_left, max_right) + 1 traverse(root) return max_diameter # ITERATIVE SOLUTION: class Solution: def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int: if not root: return 0 stack = [] heights = dict() # node -> height max_diameter = 0 node = root last_visited = None while stack or node: # Go as left as possible if node: stack.append(node) node = node.left else: peek = stack[-1] # If right child exists and not yet processed if peek.right and last_visited != peek.right: node = peek.right else: # Both children processed, now process node itself left_height = heights.get(peek.left, 0) right_height = heights.get(peek.right, 0) heights[peek] = 1 + max(left_height, right_height) max_diameter = max(max_diameter, left_height + right_height) last_visited = stack.pop() node = None # Don't go down left again return max_diameter

   Code Snippet 9: Diameter of Binary Tree (543)
   Pattern Extraction

   Core Insight: The diameter passes through some node as left_height + right_height. At each node during post-order traversal, compute both the height (for parent) and the path through this node (for global max). Pattern Name: Post-Order with Global Maximum Tracking Canonical Section: Trees > Recursive Measure Properties Recognition Signals:

   • “Longest path between any two nodes”
   • Path doesn’t have to pass through the root
   • Measured in edges (not nodes)

   Anti-Signals:

   • Longest root-to-leaf path – just the height
   • Maximum path SUM (not length) – same structure but with values. Connects to LC 124

   Decision Point: Same dual-tracking pattern as LC 124: return height upward, track diameter globally. Diameter = height without values; path sum = height with values.

   Pitfalls and Misconceptions

   1. Trap: Only considering paths through the root. Why: The longest path might be entirely within a subtree. The global max must be updated at every node. Correction: At each node: diameter_candidate = left_h + right_h. Update self.max_diameter. Return 1 + max(left_h, right_h) upward.
   2. Trap: Counting nodes instead of edges in the diameter. Why: Diameter is measured in edges. A single-node tree has diameter 0, not 1. Correction: left_h + right_h counts edges through the node. No +1 needed for the diameter itself (the +1 is in the height return value).
   Problem Mutations

   1. What if you needed the actual path, not just the length? (stress-tests: length vs path) Track the path during DFS. At the node where the global max is achieved, combine the left and right paths.
   2. What if the tree were a graph? (stress-tests: tree structure) For a tree (graph with no cycles), two BFS passes find the diameter: BFS from any node to the farthest, then BFS from that node. The second BFS’s farthest distance is the diameter.
   3. What if you needed the maximum path sum instead of length? (stress-tests: unweighted vs weighted) Track sums instead of counts, clamp negative subtrees to 0. This IS LC 124.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Diameter of Binary Tree generated via batch canonical enrichment pass.
   

3. Balanced Binary Tree (110)

   Being balanced is about having a height diff tolerance of 1.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

   # Recursive Post-Order DFS with State Threading class Solution: def isBalanced(self, root: Optional[TreeNode]) -> bool: def check(node): if not node: return True, 0 left_balanced, left_height = check(node.left) right_balanced, right_height = check(node.right) # introspect, then early returns: if not left_balanced or not right_balanced: return False, 0 # introspect against height diff threshold of 1, then early returns: if abs(left_height - right_height) > 1: return False, 0 return True, 1 + max(left_height, right_height) return check(root)[0]

   Code Snippet 10: Balanced Binary Tree (110)
   Pattern Extraction

   Core Insight: A tree is balanced iff both subtrees are balanced AND their heights differ by at most 1. Post-order: compute height bottom-up, returning -1 as a sentinel for unbalanced. Pattern Name: Post-Order with Early Termination Sentinel Canonical Section: Trees > Recursive Measure Properties Recognition Signals:

   • “Is the tree height-balanced?”
   • At each node: \(|\text{left\_height} - \text{right\_height}| \leq 1\)

   Anti-Signals:

   • Need the actual heights – just return heights without the sentinel
   • Need to balance an unbalanced tree – different problem (AVL rotation)

   Decision Point: Check balance = post-order with sentinel. The sentinel (-1) short-circuits: once imbalance is detected in any subtree, propagate without further computation.

   Pitfalls and Misconceptions

   1. Trap: Computing height separately from the balance check (\(O(n^2)\)). Why: Calling height() and isBalanced() separately retraverses subtrees. Correction: Combine: return height if balanced, -1 if not. Single \(O(n)\) pass.
   2. Trap: Not checking both subtrees’ balance status AND their height difference. Why: A node can have equal-height subtrees where one subtree is itself unbalanced. Correction: Check: left subtree balanced AND right subtree balanced AND |left_h - right_h| < 1=.
   Problem Mutations

   1. What if you needed to make the tree balanced? (stress-tests: check vs fix) Collect all nodes via inorder, rebuild as a balanced BST from the sorted array. Connects to LC 108.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Balanced Binary Tree.
   

Lowest Common Ancestor (LCA) & Ancestor Queries #

• Find LCA in binary tree or BST

  • for BST, we have the luxury of an ordering that we can exploit
  • for a generic binary tree, we’d have to resort to tree-walks regardless

• Ancestor path-related questions

Problems #

1. Lowest Common Ancestor of a Binary Search Tree (235)

   As usual, recursive or iterative is up to us, the rough idea, we have to exploit the properties of the BST properly here. We are actually just searching for the split point.

   1 2 3 4 5 6 7 8 9 10 11 12 13

   class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': """ We're searching for the node in which the two fork out, and we do a root-to-intermediate node walk for this. """ curr = root while curr: if p.val < curr.val and q.val < curr.val: curr = curr.left elif p.val > curr.val and q.val > curr.val: curr = curr.right else: return curr

   Code Snippet 11: Lowest Common Ancestor of a Binary Search Tree (235) – iterative

   1 2 3 4 5 6 7

   class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': if p.val < root.val and q.val < root.val: return self.lowestCommonAncestor(root.left, p, q) if p.val > root.val and q.val > root.val: return self.lowestCommonAncestor(root.right, p, q) return root

   Code Snippet 12: Lowest Common Ancestor of a Binary Search Tree (235) – recursive
   Pattern Extraction

   Core Insight: In a BST, the LCA is the first node where \(p\) and \(q\) split into different subtrees: one goes left, the other goes right. Follow the BST ordering to find this split point in \(O(h)\). Pattern Name: BST LCA via Split Point Canonical Section: Trees > Ancestor Queries Recognition Signals:

   • “LCA in a BST” (not a general binary tree)
   • BST ordering eliminates the need to search both subtrees
   • \(O(h)\) time, no need to visit every node

   Anti-Signals:

   • General binary tree (not BST) – must recurse both subtrees. That’s LC 236
   • Parent pointers available – intersection of two linked lists

   Decision Point: BST = follow ordering (\(O(h)\)). General BT = recurse both subtrees (\(O(n)\)). The BST property is what makes this simpler.

   Pitfalls and Misconceptions

   1. Trap: Using the general binary tree LCA algorithm (LC 236) instead of exploiting BST ordering. Why: Works but is \(O(n)\) instead of \(O(h)\). Wastes the BST property. Correction: If both \(p\) and \(q\) are less than node.val, go left. If both are greater, go right. Otherwise, node is the LCA.
   2. Trap: Forgetting the case where one of the targets IS the current node. Why: If node.val = p.val=, then node is the LCA (the other target must be in its subtree). Correction: The “split” condition naturally handles this: if p < node.val <= q= (or vice versa), node is the LCA.
   Problem Mutations

   1. What if the tree were a general binary tree? (stress-tests: BST property) Must recurse into both subtrees. Connects to LC 236.
   2. What if there were many LCA queries on the same tree? (stress-tests: single query) Preprocess with Euler tour + sparse table for \(O(1)\) per query after \(O(n)\) preprocessing. Or binary lifting for \(O(n \log n)\) preprocessing and \(O(\log n)\) per query.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for LCA of Binary Search Tree generated via batch canonical enrichment pass.
   

2. Lowest Common Ancestor (236)

   This question is intentionally there to juxtapose with problem 235. Here we can’t exploit the binary search tree property. Our objective is to chart out root to node then look for the split point.

   For the iterative DFS version, we need to preprocess and keep track of parents, then we walk up one of them and then comparatively walk up the other one until we reach it.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

   # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': """ Here we need to do a node to root walk of sorts, so we'd need to encode the child to parent directionality. We shall do this without modifying the original class for treenode by just using a simple dict. """ # trivial early returns if not root: return None stack = [(root, None)] # node, parent node_to_parent = {root: None} # maps node to parent, this allows us to keep in the parent data. # find both p and q: while p not in node_to_parent or q not in node_to_parent: node, parent = stack.pop() node_to_parent[node] = parent if node.left: stack.append((node.left, node)) if node.right: stack.append((node.right, node)) # now with preprocessed info, we get ancestors: ancestors = set() while p: ancestors.add(p) p = node_to_parent[p] # now traverse q, comparatively, which would exit as soon as q is in the ancestor set while q not in ancestors: q = node_to_parent[q] return q

   Code Snippet 13: Lowest Common Ancestor (236) – iterative DFS

   The recursive one is straightforward too, we just have to check things correctly:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

   #+begin_src python -n # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode': # Base case: if root is None or root matches p or q (either one) if not root or root == p or root == q: return root # Recur for left and right subtrees left = self.lowestCommonAncestor(root.left, p, q) right = self.lowestCommonAncestor(root.right, p, q) # If both left and right are non-null, this is the LCA if left and right: return root # Otherwise return the non-null child (either left or right) return left if left else right

   Code Snippet 14: Lowest Common Ancestor (236) – recursive DFS
   Pattern Extraction

   Core Insight: Recurse into both subtrees. If a node IS one of the targets, it’s the LCA (the other must be in its subtree). If both subtrees return non-null, the current node is the LCA. Otherwise, propagate whichever side returned non-null. Pattern Name: Recursive LCA with Return-Value Propagation Canonical Section: Trees > Ancestor Queries Recognition Signals:

   • “Find the lowest common ancestor of two nodes”
   • Both nodes are guaranteed to exist in the tree
   • General binary tree (not BST)

   Anti-Signals:

   • BST – exploit ordering: LCA is the first node where p and q split to different subtrees. Connects to LC 235
   • Parent pointers available – convert to “intersection of two linked lists” problem
   • Multiple queries – preprocess with Euler tour + sparse table for \(O(1)\) per query

   Decision Point: General BT = recursive LCA. BST = follow ordering property. Parent pointers = intersection of two linked lists (LC 160 pattern).

   Pitfalls and Misconceptions

   1. Trap: Not handling the case where one target is an ancestor of the other. Why: If p is an ancestor of q, then p itself IS the LCA. The check if root = p or root = q: return root handles this case by returning before recursing into subtrees. Correction: The base case if root in (None, p, q): return root is sufficient.
   2. Trap: Assuming both nodes exist without checking. Why: If one node doesn’t exist, the algorithm returns the other node as the “LCA”, which is wrong. Correction: The problem guarantees both nodes exist. If not guaranteed, a two-pass approach (first verify existence, then find LCA) is needed.
   Problem Mutations

   1. What if the tree were a BST? (stress-tests: tree type) LCA is the first node where p.val and q.val split to different subtrees: p.val < node.val <= q.val=. \(O(h)\) without visiting both subtrees. Connects to LC 235.
   2. What if you had many LCA queries? (stress-tests: single query) Preprocess with Euler tour + sparse table (range minimum query) for \(O(n)\) preprocessing and \(O(1)\) per query. Or binary lifting for \(O(n \log n)\) preprocessing and \(O(\log n)\) per query.
   3. What if you needed the LCA of three or more nodes? (stress-tests: two targets) LCA of multiple nodes is the LCA of the two most “distant” nodes. Or iteratively: lca(a, b, c) = lca(lca(a, b), c).
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Lowest Common Ancestor of Binary Tree generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

Binary Search Tree (BST) Properties #

• The key idea here is that we can exploit invariants that BSTs have in terms of ordering of nodes and all that.
• Validate BSTs, find kth smallest, insert/delete nodes

Problems #

1. Validate BST (98)

   we can’t just be concerned about the local nodes and check left vs right with respect to a particular parent node; it’s an accumulation of the whole range, influenced from the root itself!

   This means that we’d have to keep track of range (low, high) for each branch that we’re looking into. It’s fine for us to just do a BFS and keep this range within the tuple statistics

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

   from collections import deque class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: """ Here, we carry out a simple BFS, keeping track of the cover-range. We've chosen to use exclusive ranges in the range values below. """ queue = deque([(root, -float('inf'), float('inf'))]) # node, lower and upper while queue: # exclusive bounds node, lower, upper = queue.popleft() if not node: continue if not(lower < node.val < upper): return False if node.left: # constricts left, so new upper = node.val queue.append((node.left, lower, node.val)) if node.right: # constricts right, so new lower = node.val queue.append((node.right, node.val, upper)) return True

   Code Snippet 15: Validate BST (98) – iterative solution

   1 2 3 4 5 6 7 8 9 10 11 12 13

   class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: def validate(node, lower, upper): if not node: return True if not (lower < node.val < upper): return False return (validate(node.left, lower, node.val) and validate(node.right, node.val, upper)) return validate(root, float('-inf'), float('inf'))

   Code Snippet 16: Validate BST (98) – recursive solution
   Pattern Extraction

   Core Insight: Each node must satisfy lower_bound < node.val < upper_bound, where bounds are inherited from ancestors. The left child tightens the upper bound; the right child tightens the lower bound. Pattern Name: Recursive Bound Propagation Canonical Section: Trees > BST Property Validation Recognition Signals:

   • “Validate BST” or “check if tree satisfies ordering property”
   • Each node is constrained by its ancestors, not just its immediate parent
   • Alternative: in-order traversal should produce a strictly increasing sequence

   Anti-Signals:

   • Only checking parent-child relationships (not propagated bounds) – gives wrong answer
   • Need to construct a BST, not validate one – different problem

   Decision Point: Two approaches: (1) recursive with bound propagation, (2) in-order traversal checking strictly increasing. Both are \(O(n)\). Bound propagation is more general; in-order is simpler for BST.

   Pitfalls and Misconceptions

   1. Trap: Only checking left.val < node.val < right.val (parent-child only). Why: A node deep in the left subtree might violate the root’s constraint while satisfying its parent’s constraint. Example: root=5, left=4, left.right=6. Here 6 > 4 (valid parent-child) but 6 > 5 (violates BST property). Correction: Propagate bounds: validate(node, lower_bound, upper_bound).
   2. Trap: Initialising bounds as float('-inf') and float('inf') but using <== instead of < for comparison. Why: BST requires strict inequality. Equal values in different subtrees violate BST property (by the standard definition used in LC). Correction: Use strict inequality: lower < node.val < upper.
   Problem Mutations

   1. What if equal values were allowed in the left subtree? (stress-tests: strict inequality) Change the left bound check to lower < node.val < upper=. The definition of BST varies by source.
   2. What if you needed to find the two swapped nodes in an invalid BST? (stress-tests: validation vs repair) In-order traversal; find the two positions where the increasing property breaks. Swap those two nodes. Connects to LC 99 Recover Binary Search Tree.
   3. What if the tree were given as an array (not linked nodes)? (stress-tests: tree representation) Same bound propagation but index into the array: left child at 2i+1, right at 2i+2.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Validate BST generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

2. Kth Smallest Element in BST (230) It’s clearly an inorder traversal because inorder BST traversal gives a sorted order, which we then just use the counter variable to determine which is the one:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

   class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: stack = [root] curr = root while stack or curr: # go as left as possible, keep adding to the stack: while curr: stack.append(curr) curr = curr.left # process node, get from the stack: curr = stack.pop() k -= 1 if k == 0: return curr.val # go right subtree curr = curr.right

   Code Snippet 17: Kth Smallest Element in BST (230) – iterative dfs (optimal)

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

   class Solution: def kthSmallest(self, root: Optional[TreeNode], k: int) -> int: self.k = k self.res = None def inorder(node): if not node or self.res is not None: return # left recurse inorder(node.left) # handle this node self.k -= 1 if self.k == 0: self.res = node.val return # handle right inorder(node.right) inorder(root) return self.res

   Code Snippet 18: Kth Smallest Element in BST (230) – recursive dfs
   Pattern Extraction

   Core Insight: In-order traversal of a BST produces elements in sorted order. The $k$-th element visited is the answer. Early termination avoids traversing the entire tree. Pattern Name: In-Order Traversal with Counter Canonical Section: Trees > BST Property Exploitation Recognition Signals:

   • “$k$-th smallest/largest in BST”
   • BST property guarantees sorted in-order traversal
   • Single query (\(k\) is fixed)

   Anti-Signals:

   • Frequent queries with tree modifications – augment nodes with subtree sizes for \(O(h)\) per query
   • Not a BST – can’t exploit ordering; must use a heap or selection algorithm

   Decision Point: Single query = in-order traversal with early exit. Multiple queries = augment with subtree sizes (order-statistic tree).

   Pitfalls and Misconceptions

   1. Trap: Completing the full in-order traversal and returning the $k$-th element from the sorted list. Why: Traverses all \(n\) nodes even when \(k \ll n\). Early termination after \(k\) nodes is \(O(k + h)\). Correction: Maintain a counter; decrement on each visit. Return when counter hits 0.
   2. Trap: Using an iterative stack-based in-order traversal but not handling the termination cleanly. Why: The iterative version requires careful management of the stack and the “visit” step. Easy to visit a node twice or skip one. Correction: The iterative pattern: push all left children, pop, visit (decrement \(k\)), move to right child. Clean and testable.
   Problem Mutations

   1. What if the BST were modified frequently and you needed repeated $k$-th queries? (stress-tests: static tree) Augment each node with a subtree_size field. Finding the $k$-th element is then \(O(h)\): compare \(k\) with left subtree size to decide direction.
   2. What if you needed the $k$-th LARGEST? (stress-tests: smallest vs largest) Reverse in-order traversal: right -> visit -> left. The $k$-th visited node is the $k$-th largest.
   3. What if the tree were a general binary tree (not BST)? (stress-tests: BST property) Can’t exploit ordering. Either sort all values (\(O(n \log n)\)) or use a min-heap/quickselect (\(O(n + k \log n)\)).
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Kth Smallest Element in BST generated via batch canonical enrichment pass.
   

3. Subtree of Another Tree (572)

   We have to just keep the subroot, traverse the OG tree and eventually check if we have the same root as the subroot.

   The solution below works in \(O(n * m)\) time, which will work based on the input constraints.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

   from collections import deque # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: if not root and not subRoot: return True if not root or not subRoot: return False def is_same(p: Optional[TreeNode], q: Optional[TreeNode]) -> bool: 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) queue = deque([root]) while queue: node = queue.popleft() same = is_same(node, subRoot) if same: return True else: left, right = node.left, node.right if left: queue.append(left) if right: queue.append(right) return False

   Code Snippet 19: Subtree of Another Tree (572) – iterative BFS approach

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   # RECURSIVE BFS APPROACH class Solution: def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool: if not root: return False if self.is_same(root, subRoot): return True return self.isSubtree(root.left, subRoot) or self.isSubtree(root.right, subRoot) def is_same(self, 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 self.is_same(p.left, q.left) and self.is_same(p.right, q.right)

   Code Snippet 20: Subtree of Another Tree (572) – recursive BFS approach
   Pattern Extraction

   Core Insight: For each node in the main tree, check if the subtree rooted there is identical to the target tree. Two recursive functions: isSubtree (traverses main tree) and isSameTree (compares two trees node by node). Pattern Name: Nested Tree Comparison Canonical Section: Trees > Tree Comparison Recognition Signals:

   • “Is tree \(t\) a subtree of tree \(s\)?”
   • Need structural + value equality from some node downward

   Anti-Signals:

   • Just check if trees are identical – single isSameTree call
   • Check if one tree is a substructure (subset of paths, not full subtree) – different comparison

   Decision Point: Subtree = exact match from some node. Substructure = partial match. Subtree requires complete subtree equality; substructure allows extra nodes in the larger tree.

   Pitfalls and Misconceptions

   1. Trap: Only checking root values, not full subtree structure. Why: Two subtrees can have the same root value but different structures. Correction: isSameTree must recursively verify every node.
   2. Trap: Not handling null cases correctly in isSameTree. Why: Both null = True. One null, one not = False. Both non-null = compare values and recurse. Correction: Base cases: if not p and not q: return True; if not p or not q: return False.
   Problem Mutations

   1. What if the tree were very large? (stress-tests: \(O(mn)\) naive) Serialize both trees and use string matching (KMP or hashing) for \(O(m + n)\). Or use tree hashing.
   2. What if you needed to count the number of occurrences of \(t\) in \(s\)? (stress-tests: existence vs count) Same nested comparison but count matches instead of early returning.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Subtree of Another Tree.
   

Tree Construction & Serialization #

• Construct trees from traversal arrays, using the implicit properties that traversals give
• Serialize and deserialize trees for storage/transmission

Problems #

1. 😈 Serialize and Deserialize Binary Tree (297) We can do this by properly having level-order traversals, which we can also prune by removing all the trailing nulls. For the deserialisation, since it is inorder, we can just “walk it level by level” since it’s representing a BFS.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

   # Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None from collections import deque class Codec: def serialize(self, root): """Encodes a tree to a single string. :type root: TreeNode :rtype: str """ if not root: return "null" result = [] queue = deque([root]) while queue: node = queue.popleft() if node: result.append(str(node.val)) queue.append(node.left) queue.append(node.right) else: result.append("null") # trim trailing nulls (on the final result), help to reduce size since trailing nulls unncessary while result and result[-1] == "null": result.pop() return ",".join(result) def deserialize(self, data): """Decodes your encoded data to tree. :type data: str :rtype: TreeNode """ if data == "null": return None nodes = data.split(",") root = TreeNode(int(nodes[0])) queue = deque([root]) idx = 1 while queue: node = queue.popleft() # handle left branch if non-null if idx < len(nodes): if nodes[idx] != "null": node.left = TreeNode(int(nodes[idx])) queue.append(node.left) idx += 1 # handle right branch if non-null if idx < len(nodes): if nodes[idx] != "null": node.right = TreeNode(int(nodes[idx])) queue.append(node.right) idx += 1 return root

   Code Snippet 21: Serialize and Deserialize Binary Tree (297)
   Pattern Extraction

   Core Insight: Use preorder traversal with null markers (e.g., "N") to uniquely encode the tree structure. Deserialize by consuming tokens sequentially, recursing left then right. Pattern Name: Preorder Serialization with Null Markers Canonical Section: Trees > Serialization Recognition Signals:

   • “Convert tree to string and back”
   • Must preserve exact tree structure (not just values)
   • Null children must be encoded to distinguish subtree shapes

   Anti-Signals:

   • Only need to encode values (structure is implicit, e.g., BST) – can use sorted insert
   • Need human-readable format – consider JSON or nested parentheses

   Decision Point: General binary tree: preorder + null markers. BST specifically: preorder without null markers (structure is recoverable from BST property). Level-order also works but preorder is simpler recursively.

   Pitfalls and Misconceptions

   1. Trap: Not encoding null children, making deserialization ambiguous. Why: Without null markers, the tree [1, 2] (2 is left child) and [1, null, 2] (2 is right child) produce the same preorder sequence. Correction: Encode null children as a sentinel (e.g., "N" or "#").
   2. Trap: Using a global index variable that doesn’t persist across recursive calls in Python. Why: Python integers are immutable; modifying a “global” int in a nested function doesn’t propagate. Correction: Use a mutable container (deque with popleft(), iterator, or self.idx) that persists across recursive calls.
   Problem Mutations

   1. What if the tree were a BST? (stress-tests: general binary tree) Don’t need null markers. Preorder traversal + BST property uniquely determines the tree. Deserialize using value bounds to decide when to stop recursing left.
   2. What if the tree were N-ary? (stress-tests: binary) Encode the number of children per node, or use end-of-children markers. The serialization format needs to capture variable fan-out.
   3. What if you needed compact serialization (minimal space)? (stress-tests: simplicity vs efficiency) Bit-level encoding: one bit per null marker, packed values. Much more complex but smaller output.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Serialize and Deserialize Binary Tree generated via batch canonical enrichment pass.
   

2. ⭐️ Construct Binary Tree from Traversals (105)

   • here we need to exploit the following properties:

     • for inorder traversal, we can keep partitioning left and right parts of the array to get left and right sub-trees!

     • The key insight is that the preorder sequence gives you the root, and the inorder sequence tells you how to split the tree. Recursively applying this builds the tree efficiently.

       Even better, we can use generators to make things efficient.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

   class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: idx_map = {val: i for i, val in enumerate(inorder)} preorder_index = 0 def helper(left, right): nonlocal preorder_index if left > right: return None root_val = preorder[preorder_index] preorder_index += 1 root = TreeNode(root_val) # Build left and right subtrees root.left = helper(left, idx_map[root_val] - 1) root.right = helper(idx_map[root_val] + 1, right) return root return helper(0, len(inorder) - 1)

   Code Snippet 22: Construct Binary Tree from Traversals (105) – standard approach

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   class Solution: def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]: inorder_val_to_idx = {val: idx for idx, val in enumerate(inorder)} preorder_iter = iter(preorder) # Create a generator from preorder def helper(left, right): if left > right: return None root_val = next(preorder_iter) # Get the next root value from the generator root = TreeNode(root_val) inorder_idx = inorder_val_to_idx[root_val] root.left = helper(left, inorder_idx - 1) root.right = helper(inorder_idx + 1, right) return root return helper(0, len(inorder) - 1)

   Code Snippet 23: Construct Binary Tree from Traversals (105) – using generators
   Pattern Extraction

   Core Insight: The first element of preorder is always the root. Find this root in inorder to split inorder into left and right subtrees. The split sizes determine how many preorder elements belong to each subtree. Recurse. Pattern Name: Recursive Tree Construction from Dual Traversals Canonical Section: Trees > Construction Recognition Signals:

   • “Construct tree from preorder + inorder” (or postorder + inorder)
   • Need both traversals (a single traversal is ambiguous without null markers)
   • Recursive divide using the root-finding step

   Anti-Signals:

   • Given preorder + postorder (without inorder) – ambiguous for general binary trees (works for full binary trees)
   • Given level-order + inorder – different reconstruction algorithm

   Decision Point: Preorder gives roots (first element). Postorder gives roots (last element). Inorder provides the left/right split. You need inorder plus one of {preorder, postorder} for unique reconstruction.

   Pitfalls and Misconceptions

   1. Trap: Linearly searching for the root in inorder at each recursive step (\(O(n)\) per level). Why: Without a hash map, each root-finding is \(O(n)\), making the total \(O(n^2)\). Correction: Precompute a hash map: inorder_index = {val: i for i, val in enumerate(inorder)}. \(O(1)\) root lookup, \(O(n)\) total.
   2. Trap: Getting the preorder slice boundaries wrong. Why: The number of elements in the left subtree = root_index_in_inorder - inorder_start. This count determines how many preorder elements belong to the left subtree. Correction: left_size = root_idx - in_start. Left preorder: [pre_start+1, pre_start+1+left_size). Right preorder: [pre_start+1+left_size, pre_end).
   Problem Mutations

   1. What if you had postorder + inorder instead of preorder + inorder? (stress-tests: traversal type) Postorder’s last element is the root (not first). Mirror the logic: find root in inorder, recurse on right subtree first (postorder visits right before root). Connects to LC 106.
   2. What if values could have duplicates? (stress-tests: unique values) The hash map approach breaks (multiple indices for the same value). Need additional disambiguation or constraint.
   3. What if you needed to construct from preorder traversal only (for a BST)? (stress-tests: general tree) BST property provides implicit inorder (sorted). Or: use value bounds recursively to decide when to stop building left subtrees.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Construct Binary Tree from Traversals generated via batch canonical enrichment pass.
   

Path Sum & Root-to-Leaf Problems #

• Compute or find root-to-leaf path sums or paths satisfying conditions

Problems #

1. Path Sum (112) It’s really just a depth-focused traversal, here I just did it as a pre-ordered traversal. I notice that in these questions, building up from requirements is a good way to make sure that the logic is clear and there are no unnecessary hiccups when implementing things.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

   # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = vkl # self.left = left # self.right = right class Solution: def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool: if not root: return False stack = [(root, root.val)] while stack: node, curr_sum = stack.pop() if not node.left and not node.right and curr_sum == targetSum: return True if node.left: stack.append((node.left, curr_sum + node.left.val)) if node.right: stack.append((node.right, curr_sum + node.right.val)) return False

   Code Snippet 24: Path Sum (112)
   Pattern Extraction

   Core Insight: DFS from root to leaves, tracking the running sum. A leaf node (no children) with running sum equal to the target is a success. Pattern Name: Root-to-Leaf DFS with Running Accumulator Canonical Section: Trees > Path Sum Problems Recognition Signals:

   • “Does any root-to-leaf path sum to target?”
   • Boolean output
   • Leaf = no children

   Anti-Signals:

   • Path doesn’t have to end at a leaf – different problem
   • Need all paths, not just existence – backtracking (LC 113)
   • Path can start/end anywhere – LC 124 style

   Decision Point: Root-to-leaf = DFS with leaf check. Any-node path = dual tracking (contribution + global). The endpoint constraint determines the approach.

   Pitfalls and Misconceptions

   1. Trap: Checking remaining = 0= at every node, not just leaves. Why: A non-leaf node with zero remaining doesn’t mean a valid path exists (the path must end at a leaf). Correction: Only return True when not node.left and not node.right and remaining = 0=.
   Problem Mutations

   1. What if you needed all paths, not just existence? (stress-tests: boolean vs enumeration) Backtracking: collect path during DFS, add to results at valid leaves. Connects to LC 113.
   2. What if the path could start at any node? (stress-tests: root-to-leaf) At each node, run a DFS for paths starting there. \(O(n^2)\) naive. Connects to LC 437 Path Sum III (prefix sum variant).
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Path Sum.
   

2. Path Sum II (113)

   This is a simple extension that requires us to keep note of the paths that are created. Yet again, the desire to just get it working without falling into deviations because of micro-optimisations helped.

   For example, in the accumulation below, we could have kept the state accumulation leaner (e.g. by keeping path of nodes then formatting as a final step to give us the value-based paths) but it wasn’t necessary, the non-optimised version is already globally superior.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

   class Solution: def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]: """ We wish to have a depth-focused traversal and we shall accumulate the paths for it. A path is a list of node values. """ if not root: return [] stack = [(root, root.val, [root.val])] # curr_node, curr_sum, path paths = [] while stack: node, curr_sum, path = stack.pop() if not node.left and not node.right and curr_sum == targetSum: paths.append(path) if node.left: stack.append((node.left, node.left.val + curr_sum, path + [node.left.val])) if node.right: stack.append((node.right, node.right.val + curr_sum, path + [node.right.val])) return paths

   Code Snippet 25: Path Sum II (113)
   Pattern Extraction

   Core Insight: DFS with backtracking. Maintain a running path and remaining sum. When a leaf is reached with remaining = 0, copy the path to results. Pattern Name: Root-to-Leaf DFS with Backtracking Canonical Section: Trees > Path Sum Problems Recognition Signals:

   • “Find ALL root-to-leaf paths summing to target”
   • Collect paths, not just existence
   • Backtracking to explore all branches

   Anti-Signals:

   • Only need existence (boolean) – simpler, no backtracking needed (LC 112)

   Decision Point: Boolean = simple DFS. Enumerate = DFS with backtracking and path collection.

   Pitfalls and Misconceptions

   1. Trap: Not making a copy of the path when adding to results. Why: The path list is mutated during backtracking. Without copying, all results point to the same empty list. Correction: results.append(path[:]).
   2. Trap: Forgetting to backtrack (path.pop()) after exploring a subtree. Why: Without backtracking, the path accumulates all visited nodes, producing invalid paths. Correction: After recursing into left/right, path.pop().
   Problem Mutations

   1. What if the path could start at any node and end at any node? (stress-tests: root-to-leaf) Different approach: prefix sum DFS. Connects to LC 437 Path Sum III.
   2. What if you needed the path with maximum sum? (stress-tests: target sum) Post-order with dual tracking. Connects to LC 124.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Path Sum II.
   

3. ⭐️😈 Binary Tree Maximum Path Sum(124)

   We have to keep track of gain as we do DFS (post-order). We just need to keep accumulating max upward gain, as though we’re walking back up from leaf to root. Here’s a state-threaded version:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77

   class Solution: def maxPathSum(self, root: Optional['TreeNode']) -> int: """ We choose to do a recursive dfs here, which the intent of accumulating max path_sum so far. We acknowledge that it's any (partial) path, doesn't have to be a root-to-leaf path. """ def dfs(node: Optional['TreeNode'], current_max: int) -> Tuple[int, int]: """ We shall return (max_gain_upwards, max_path_sum_so_far) from this helper. For determining the gain, there's a need to pick the best of (left_branch, right_branch) since they are mutually exclusive choices. """ if not node: return ( 0, # no max gain upwards current_max # path sum so far is current max unchanged. ) left_gain, current_max = dfs(node.left, current_max) right_gain, current_max = dfs(node.right, current_max) left_gain = max(left_gain, 0) # here we choose to either include or exclude (and use 0) right_gain = max(right_gain, 0) price_newpath = node.val + left_gain + right_gain current_max = max(current_max, price_newpath) # here, a choice has to be made on whether to pick left or right branch. max_gain_upwards = node.val + max(left_gain, right_gain) return max_gain_upwards, current_max _, max_sum = dfs(root, float('-inf')) return max_sum # FOR DEMO: HERE'S AN ITERATIVE VERSION (super complex though): from typing import Optional class Solution: def maxPathSum(self, root: Optional['TreeNode']) -> int: if not root: return 0 stack = [] gains = {} # Map node -> max gain upwards max_sum = float('-inf') last_visited = None node = root while stack or node: if node: stack.append(node) node = node.left else: peek_node = stack[-1] # If right child of the recently visited node exists and not processed yet, process right subtree first if peek_node.right and last_visited != peek_node.right: node = peek_node.right else: # Post-order processing: stack.pop() # Get left and right gains, ceiling-ed by 0 left_gain = max(gains.get(peek_node.left, 0), 0) right_gain = max(gains.get(peek_node.right, 0), 0) # Price of new path split at this node current_path_sum = peek_node.val + left_gain + right_gain max_sum = max(max_sum, current_path_sum) # Max gain returning to parent gains[peek_node] = peek_node.val + max(left_gain, right_gain) last_visited = peek_node return max_sum

   Code Snippet 26: Binary Tree Maximum Path Sum(124)
   Pattern Extraction

   Core Insight: At each node, the maximum path through it uses at most one side (left OR right) when contributing upward, but can use BOTH sides for the global answer. Track two things: the max contribution upward (for parents) and the max path through this node (for the global answer). Pattern Name: Post-Order with Dual Tracking (contribution vs global) Canonical Section: Trees > Path Sum Problems Recognition Signals:

   • “Maximum path sum” where path can start/end at ANY node
   • Path doesn’t have to pass through the root
   • Negative values are possible (might be better to exclude subtrees)
   • Need to distinguish “contribution to parent” from “best path through this node”

   Anti-Signals:

   • Path must start at root and end at a leaf – simpler, standard DFS with running sum
   • All values are non-negative – every node is included, just find the longest path

   Decision Point: The crux is the dual tracking: max_gain(node) = node.val + max(left_gain, right_gain, 0) (clamped to 0 because negative contributions are worse than skipping). Global answer considers node.val + left_gain + right_gain (using both sides). Interviewer Comms: “I do a post-order traversal. At each node, I compute the max gain I can offer upward: my value plus the better of my two children’s gains (clamped to zero). Separately, I update the global max with the path that goes left-through-me-to-right. The key distinction is that a node can use both children for the global answer, but only one child when contributing upward to its parent.”

   Pitfalls and Misconceptions

   1. Trap: Not clamping negative child contributions to zero. Why: A subtree with negative total gain is worse than ignoring it. Including a negative contribution reduces the path sum. Correction: left_gain = max(0, max_gain(node.left)). Zero means “skip this subtree.”
   2. Trap: Confusing the contribution to parent with the global path sum. Why: The contribution upward can only use ONE side (the path can’t fork). The global answer CAN use both sides. Mixing these up either undercounts (missing fork paths) or overcounts (forking paths contributed upward). Correction: Return node.val + max(left_gain, right_gain) upward. Update global with node.val + left_gain + right_gain.
   3. Trap: Initialising global_max = 0 instead of float('-inf'). Why: If all values are negative, the answer is the least negative single node. Zero is not achievable. Correction: global_max = float('-inf').
   Problem Mutations

   1. What if the path had to include the root? (stress-tests: any-node start/end) Simpler: DFS from root, tracking max prefix sum in each direction. No dual tracking needed.
   2. What if the tree were a general graph? (stress-tests: tree assumption) “Longest path in a graph” is NP-hard in general. For trees, the post-order approach works because there’s a unique path between any two nodes.
   3. What if you needed to find the actual path, not just the sum? (stress-tests: sum vs path) Track parent pointers during the DFS and reconstruct the path from the node where the global max was achieved.
   4. What if path length were limited to at most \(k\) nodes? (stress-tests: unbounded path) Need to track path length alongside sum. The contribution function becomes two-dimensional: (max_sum, path_length). More complex but same post-order structure.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Standardised annotation dropdowns for Binary Tree Maximum Path Sum generated via batch canonical enrichment pass. Review against personal solving experience and adjust.
   

4. Count Good Nodes in Binary Tree (1448)

   this is a path traversal with some parent tracking, it’s going to apply for all the levels, so we can just do level order traversal (BFS) and get the job done:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   from collections import deque class Solution: def goodNodes(self, root: TreeNode) -> int: queue = deque([(root, root.val)]) count = 0 while queue: node, max_above = queue.popleft() if node.val >= max_above: count += 1 max_new = max(max_above, node.val) if node.left: queue.append((node.left, max_new)) if node.right: queue.append((node.right, max_new)) return count

   Code Snippet 27: Count Good Nodes in Binary Tree (1448)

   However, the canonically optimal solution is to use a DFS (here it’s an iterative pre-order DFS) for this:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

   class Solution: def goodNodes(self, root: TreeNode) -> int: if not root: return 0 stack = [(root, root.val)] # Each entry: (node, max_above) count = 0 while stack: node, max_above = stack.pop() if node.val >= max_above: count += 1 max_new = max(max_above, node.val) # Push children with updated max_above if node.left: stack.append((node.left, max_new)) if node.right: stack.append((node.right, max_new)) return count

   Code Snippet 28: Count Good Nodes in Binary Tree (1448)
   Pattern Extraction

   Core Insight: DFS passing the maximum value seen on the path from root to current node. A node is “good” if its value \(\geq\) the running max. Pattern Name: Top-Down DFS with Running Max Canonical Section: Trees > Path Property Tracking Recognition Signals:

   • “Good node” = no ancestor with greater value
   • Top-down information propagation (max from root)

   Anti-Signals:

   • Bottom-up computation (needs children info first) – postorder
   • Need to compare with all ancestors, not just max – more complex tracking

   Decision Point: Top-down property = pass information DOWN during DFS. Bottom-up property = return information UP during DFS.

   Pitfalls and Misconceptions

   1. Trap: Using a global max instead of a path max. Why: The max should be specific to the current root-to-node path, not the global max across all nodes. Correction: Pass max_so_far as a parameter, updated with max(max_so_far, node.val) at each step.
   Problem Mutations

   1. What if “good” meant strictly greater than all ancestors? (stress-tests: greater-or-equal) Change the comparison to node.val > max_so_far. Same algorithm, different predicate.
   AI usage disclosure Claude Opus 4.6 · content enrichment

   Batch annotation for Count Good Nodes in Binary Tree.
   

Tree Transformations & Flattening #

• Modify tree structure, flatten trees to linked list representations

Problems #

1. TODO Flatten Binary Tree to Linked List (114)

SOE #

1. FORGETTING TO EXPLOIT THE PROPERTIS OF A BST!!! (it’s already ordered bro)

2. Null or empty tree edge cases

3. Infinite recursion or missing base condition

4. Forgetting to track visited nodes for graphs/trees that can have cycles

5. MIXING UP root to leaf path from leaf to root path.

   • note that following parent pointer usually ends up creating leaf to root path, hence we might need to reverse it.

6. Having the wrong mental model:

   • height is about edge counting, not about counting nodes / vertices

7. Incorrect traversal order or index misalignment

8. Previous Misconceptions:

   1. Not every DAG is a tree, a DAG is a superset of a tree. Therefore, to do things like tree-validity checks, we can’t do Kahn’s algo topo-sorting and all that.

Decision Flow #

1. Need traversal?

   • Use DFS (recursive/preorder/inorder/postorder or iterative) or BFS (level-order).
     • BFS: For level-by-level processing, shortest path in unweighted trees.
     • Recursive DFS: Simple for most cases (call stack manages state naturally).
     • Iterative DFS/BFS: Use stacks or queues.
     • Side note: For iterative postorder, use either reversal trick (no visited tracking) or one-stack with `last_visited` for true child-completion semantics.

2. When to use visited/last_visited tracking?

   • Needed for iterative postorder (true left-right-root, no reversal buffer) to guarantee child-to-parent order.
   • Required for any graph/tree traversal with possible cycles (general graphs) to prevent revisiting.
   • Use parent-tracking for reconstructing ancestry/path information, e.g., for LCA or path queries.

3. Tree construction or serialization?

   • Use level-order traversal (BFS) for serialization/deserialization as with Leetcode 297.
   • Recursive divide and conquer for tree construction from traversals (e.g., build tree from inorder & preorder/postorder).

4. Query path sums or conditions?

   • DFS with state tracking (either as args or via return values).
   • Example: Accumulate max gain or sum along path, propagate partial results upwards.

5. Validate BST?

   • Inorder traversal (check for sorted order).
   • Use explicit min/max value constraints during traversal.

6. Lowest Common Ancestor (LCA) queries?

   • Recursive “found in left/right” checking with backtracking, or use BFS/DFS to record parent pointers for fast ancestor checks.

7. Which iterative traversal to use?

   • Simple result? → Use reversal trick for postorder.
   • Need true postorder decision points? → Use last_visited/visited tracking.
   • Need to reconstruct path? → Maintain parent pointers during traversal.

Tips #

1. Only reverse results (reversal trick) for postorder if you don’t need strict post-traversal processing.

2. For genuine postorder-dependent logic, use last_visited tracking to ensure both children are processed.

3. Use BFS for problems where processing by levels (depth) matters or the shortest path in unweighted trees is desired.

4. For graphs, always use a visited set to avoid cycles/infinite loops.

Styles, Tricks and Boilerplate #

Styles #

Tree Property Tricks #

1. Traversal Properties that we can exploit:

   • Ability to reconstruct tree: You can reconstruct a tree from preorder + inorder, or postorder + inorder, but not from preorder + postorder alone (unless the tree is full).

   • Partitioning Properties:

     • Preorder Traversal

       • The first element is always the root of the current subtree.

     • Inorder Traversal

       • The index of the root splits the array into left and right subtrees.

     • Postorder Traversal

2. When they ask extension questions e.g. in the problem “Kth Smallest Element in a BST”, our first reach should try to augment trees into order-statistic trees.

   Only after that should we consider things like auxiliary datastructures like a minHeap or whatsoever.

Use state threading #

It’s more efficient to keep state as part of the function parameters or return values.

State threading is a technique where you pass state explicitly through function arguments, which can lead to better performance (stack allocation, cache locality), safer code (no globals), and easier reasoning (pure functions). It is especially intuitive and beneficial in recursive algorithms, dynamic programming, functional programming, and parsing.

Build the final list directly to avoid intermediate list #

See the “level order traversal problem (102)”

Boilerplate #

Tree Traversal #

Here’s the level-order traversal (BFS) implementation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

from collections import deque

def bfs(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val)  # Process the node
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

# augmenting statistics would look like this:
def level_order_with_depth(root):
    if not root:
        return
    queue = deque()
    queue.append((root, 1))  # (node, depth)
    while queue:
        node, depth = queue.popleft()
        print(f"depth = {depth}, val = {node.val}")  # or collect in a result list
        if node.left:
            queue.append((node.left, depth + 1))
        if node.right:
            queue.append((node.right, depth + 1))