5.33 Fill in the Ancestors of the Node

5.33.1 Problem Metadata

5.33.2 Description

Given a binary tree and a target node value, find and return all ancestors of the target node (from the node’s parent up to the root).

5.33.3 Examples

Input: root = [1,2,3,4,5], key = 5
Output: [2, 1]
Explanation: Node 5's parent is 2, and 2's parent is 1 (root)

       1
      / \
     2   3
    / \
   4   5

5.33.4 Solution - DFS Path Building

5.33.4.1 Walkthrough

Use DFS to search for the target node. When found, backtrack and collect ancestors along the path.

Core Strategy:

  1. Recursively search left and right subtrees for the target
  2. When target is found, return true to signal success
  3. On the way back up, add each node to the ancestors list

Example: Find ancestors of 5 in [1,2,3,4,5]:

DFS path: 1 → 2 → 4 (not found) → backtrack → 5 (found!)
Backtrack: 5 found → add 2 to ancestors → add 1 to ancestors
Result: [2, 1]

5.33.4.2 Analysis

  • Time Complexity: O(n) - Visit each node once in worst case
  • Space Complexity: O(h) - Recursion stack depth

5.33.4.3 Implementation Steps

  1. If root is null, return false.
  2. If root matches key, return true (found).
  3. Recursively check left and right children.
  4. If either returns true, add current node to ancestors and return true.

5.33.4.4 Code - Java

public boolean printAncestors(TreeNode root, int key, List<Integer> ancestors) {
    if (root == null) {
        return false;
    }
    if (root.val == key) {
        return true;
    }
    if (printAncestors(root.left, key, ancestors) || printAncestors(root.right, key, ancestors)) {
        ancestors.add(root.val);
        return true;
    }
    return false;
}