25 BST Delete, Analysis, and Path Problems

26 BST Delete, Analysis, and Path Problems

Week 2, Session 1. CSS 343.

26.1 Warmup

class Solution {
 public:
  bool isSymmetric(TreeNode* root) {
    if (root == nullptr) return true;
    return mirror(root->left, root->right);
  }
 private:
  bool mirror(TreeNode* a, TreeNode* b) {
    if (a == nullptr && b == nullptr) return true;
    if (a == nullptr || b == nullptr) return false;
    return a->val == b->val
        && mirror(a->left, b->right)
        && mirror(a->right, b->left);
  }
};

Dual recursion on a single tree — the same shape as isSameTree, with the children swapped.

26.2 Learning objectives

Implement BST delete handling all three structural cases.
Explain why sorted-insertion degenerates a BST and what the height becomes.
Write recursive functions that traverse two trees simultaneously.
Solve root-to-leaf path sum problems using accumulator-style recursion.

26.3 BST delete — three cases

Already previewed in Chapter 18. Here we do it carefully and pull it into a class.

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; }

  // value == root->data
  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 {
    // Two children: replace value with in-order successor's, delete successor.
    TreeNode* succ = findMin(root->right);
    root->data = succ->data;
    remove(root->right, succ->data);
  }
}

Trace on a tree with 50 → {30 → {20, 40}, 70 → {60, 80}}, deleting 30:

Locate 30. It has two children (20 and 40).
Find in-order successor: leftmost of right subtree of 30 → 40.
Copy 40 into the node where 30 lives. Tree now: 50 → {40 → {20, 40}, 70 → …}. (Yes, there are two 40s temporarily.)
Recurse on right subtree to delete 40. It is a leaf — straightforward.
Result: 50 → {40 → {20}, 70 → {60, 80}}.

In-order traversal still produces sorted output. The BST property is preserved.

Why not detach the node directly? Because either of its children might itself have two children. You would end up needing to graft a whole subtree somewhere. Replacing the value and deleting the source is simpler — the source by construction has no left child.

26.4 Degenerate BST

Insert {1, 2, 3, 4, 5} in sorted order:

Height n−1. Search and insert are O(n). This is why CSS 343 spends so much energy on balanced trees (Chapter 29) — they prevent degeneration by rotating.

Notice that the same input data, inserted in a different order — say {3, 1, 4, 2, 5} — produces a balanced tree:

Height 2. Search is O(log n). The data is identical; the order of insertion changed everything. Real-world BSTs cannot control their input order, so they must rebalance.

26.5 Recurrence for height

In the best case (perfectly balanced), inserting n elements gives height ⌈log₂ n⌉. Recurrence: T(n) = T(n/2) + O(1), since one comparison drops half the tree. T(n) = O(log n).

In the worst case, T(n) = T(n−1) + O(1), giving O(n).

In the average case (random insertion order), it can be shown that the expected height is O(log n). But “average” is not “worst” — and exam questions love worst cases.

26.6 Path sum problems

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 value from the target, recurse. At a leaf, check if the remainder equals the leaf value.

Variants:

Path Sum II (#113): collect all paths summing to target. Use backtracking.
Path Sum III (#437): any node-to-descendant path. More state.
Sum Root to Leaf Numbers (#129): treat the path as a number. Use target * 10 + root->val.

26.7 Dual recursion: `isSameTree`

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 marched in parallel. Three cases: both null (match), one null (mismatch), both nonempty (compare values + both children).

26.8 Invert / mirror — the famous one

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

Three lines. The one that supposedly got Max Howell rejected from Google.

26.9 Try it

Insert {50, 30, 70, 20, 40, 60, 80} into a BST, then delete 50. Draw the tree before and after. Confirm in-order traversal is still sorted.

26.10 Self-check

1. Deleting a node with two children, you replace its value with:

a. Its left child's value.
b. The minimum value in its right subtree (in-order successor).
c. A random descendant's value.
d. Zero.

b. The in-order successor (or predecessor — either works). The replacement value preserves the BST property.

2. Inserting {1, 2, 3, ..., 1000} into a plain BST gives a tree of height:

a. 10
b. ~ log₂(1000) ≈ 10
c. 999
d. 500

c. Sorted insertion degenerates to a right-spine of length n−1.

26.11 Challenges

Delete Node in a BST (#450) — implement the above.
Path Sum II (#113) — collect paths.
Sum Root to Leaf Numbers (#129).
Invert Binary Tree (#226).

26.12 Where this fits

You can now build a BST that handles insertion, search, and deletion. Next chapter wraps it in a template class with proper memory management and uses the same machinery to construct Huffman trees.

You are here	Coming up
BST delete (three cases), path sum, dual recursion	Chapter 24: template BST and Huffman coding