20  Advanced Recursion and Tree Problems

21 Advanced Recursion and Tree Problems

Week 9, Session 2. CSS 342.

21.1 Warmup

Path Sum (#112). Given a tree and a target, return true if there is a root-to-leaf path summing to the target.

class Solution {
 public:
  bool hasPathSum(TreeNode* root, int target) {
    if (root == nullptr) return false;
    if (root->left == nullptr && root->right == nullptr) {
      return target == root->val;
    }
    return hasPathSum(root->left, target - root->val)
        || hasPathSum(root->right, target - root->val);
  }
};

The accumulator pattern: subtract the current node’s value, recurse with the remainder. When you reach a leaf, the remainder should match. Beautiful.

21.2 Learning objectives

1. Apply a systematic strategy to novel recursive problems.
2. Implement BST delete handling all three cases (leaf, one child, two children).
3. Analyze the time complexity of recursive tree operations.
4. Solve LeetCode-style tree problems by decomposition.
5. Identify what balanced trees, heaps, and graphs will add in CSS 343.

21.3 The strategy

For any recursive problem:

1. What does this function return? Write down the contract in one sentence. “Returns true if the value is in the tree.” “Returns the depth of the tree.”
2. What is the base case? The smallest input. For trees that is usually nullptr. For arrays usually empty or a single element.
3. What are the recursive cases? How does the answer for the current node relate to the answers for the children/subarrays?

Write the contract. Write the base case. Trust the recursion to handle the rest.

21.4 BST delete — the hard case

Three structural cases when deleting a node:

1. Leaf (no children). Just null the parent’s pointer to it.
2. One child. Replace the node with its only child.
3. Two children. Replace the node’s value with its in-order successor’s value, then delete the successor.

TreeNode* findMin(TreeNode* node) {
  while (node->left != nullptr) node = node->left;
  return node;
}

void remove(TreeNode*& root, int value) {
  if (root == nullptr) return;
  if (value < root->data) { remove(root->left, value); return; }
  if (value > root->data) { remove(root->right, value); return; }

  // Found it.
  if (root->left == nullptr && root->right == nullptr) {
    delete root;
    root = nullptr;
  } else if (root->left == nullptr) {
    TreeNode* tmp = root;
    root = root->right;
    delete tmp;
  } else if (root->right == nullptr) {
    TreeNode* tmp = root;
    root = root->left;
    delete tmp;
  } else {
    TreeNode* succ = findMin(root->right);
    root->data = succ->data;
    remove(root->right, succ->data);    // delete the duplicate
  }
}

Three cases. The third is the only interesting one — we cannot simply detach the node, so we replace its value and delete the source of that value (which by construction has at most one child).

Some textbooks use the in-order predecessor (max of the left subtree) instead of the successor (min of the right). Either works. Mixing them in alternate deletions can keep a tree slightly more balanced, but that level of optimization is not in 342.

21.5 Tree complexity in terms of height

For a tree of height h:

Operation	Time
insert	O(h)
search	O(h)
remove	O(h)

If the tree is balanced, h = O(log n). If degenerate, h = O(n). The whole point of CSS 343’s balanced-tree chapter is guaranteeing h = O(log n).

21.6 Power set — recursive subset generation

Generate all subsets of {1, 2, 3}. There are 2³ = 8.

void powerSet(const vector<int>& nums, int i, vector<int>& current,
              vector<vector<int>>& result) {
  if (i == (int)nums.size()) {
    result.push_back(current);
    return;
  }
  // skip nums[i]
  powerSet(nums, i + 1, current, result);
  // include nums[i]
  current.push_back(nums[i]);
  powerSet(nums, i + 1, current, result);
  current.pop_back();             // backtrack
}

At each index, two recursive calls: one with the element, one without. Tree branches 2ⁿ. Total work O(n · 2ⁿ).

The current.pop_back() after the second recursive call is the backtrack — undoing the choice so the caller’s current is unchanged. This is the canonical backtracking shape and you will use it forever (8 queens, sudoku, all paths in a graph).

21.7 Mirror / invert a tree

TreeNode* invertTree(TreeNode* root) {
  if (root == nullptr) return nullptr;
  swap(root->left, root->right);
  invertTree(root->left);
  invertTree(root->right);
  return root;
}

Recurse, swap, return. Three lines plus the base case. The infamous Max Howell tweet:

Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so f*** off.

For the record: this is invertTree. Three lines. Memorize it.

21.8 Same tree — dual recursion

bool isSameTree(TreeNode* p, TreeNode* q) {
  if (p == nullptr && q == nullptr) return true;
  if (p == nullptr || q == nullptr) return false;
  return p->val == q->val
      && isSameTree(p->left, q->left)
      && isSameTree(p->right, q->right);
}

Two trees being recursed in lockstep. Three cases: both empty (match), one empty (mismatch), both nonempty (compare values + both subtrees).

21.9 CSS 343 preview

What 343 adds on top of this:

• Balanced trees (AVL, red-black): guarantee O(log n) by rebalancing on insert/delete.
• Heaps: a different shape of tree, optimized for “give me the max” — backed by an array.
• Hash tables: O(1) lookup at the cost of giving up sorted order.
• Graphs: trees with cycles allowed. BFS, DFS, Dijkstra, MST.
• Algorithm design: divide-and-conquer, greedy, dynamic programming.
• Design patterns: OOP at scale.
• Theory of computation: regex, finite automata, Turing machines.

If you can write inOrder and insert from memory, you are ready for all of it.

21.10 Try it

Implement bool symmetric(TreeNode* root) — true if the tree is a mirror image of itself. Hint: write a helper mirrorMatch(TreeNode* a, TreeNode* b) and call mirrorMatch(root->left, root->right).

bool mirrorMatch(TreeNode* a, TreeNode* b) {
  if (a == nullptr && b == nullptr) return true;
  if (a == nullptr || b == nullptr) return false;
  return a->val == b->val
      && mirrorMatch(a->left, b->right)
      && mirrorMatch(a->right, b->left);
}

bool symmetric(TreeNode* root) {
  if (root == nullptr) return true;
  return mirrorMatch(root->left, root->right);
}

21.11 Self-check

1. The hardest case for BST delete is when:

• a. The node is a leaf.
• b. The node has one child.
• c. The node has two children.
• d. The node is the root.

c. Two children: cannot detach directly. Replace with in-order successor's value, then delete the successor.

2. The power-set generator uses 2ⁿ recursive leaves. Total work?

• a. O(2ⁿ)
• b. O(n · 2ⁿ)
• c. O(n²)
• d. O(n log n)

b. Each of 2ⁿ subsets has O(n) average size to copy into result.

21.12 Challenges

1. Symmetric Tree (#101).
2. Subsets (#78) — implement the power set above.
3. Lowest Common Ancestor of BST (#235).
4. Diameter of Binary Tree (#543).

21.13 Where this fits

Last content chapter before the 342 final review. You have all the tools to take CSS 343.

You are here	Coming up
BST delete, power set, mirror, dual recursion	Chapter 19: final exam review