Problem

Given a binary tree and a target node, write a function to print or return all the ancestors of the target node in the binary tree. Ancestors of a node are all the nodes in the path from the root to the parent of the target node.

Examples

Example 1

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

 Input:
 Binary Tree:
          1
         / \
        2   3
       / \
      4   5
 Target Node: 4
 
 Output: [2, 1]
 
 Explanation:
 The ancestors of node 4 are node 2 and node 1 (starting from its parent up to the root).

Example 2

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

 Input: 
 Binary Tree:
          10
         /  \
        20   30
       /  \
      40   50
 Target Node: 50
 
 Output: [20, 10]
 
 Explanation:
 For target node 50, its ancestors in the binary tree are 20 and 10 (parent to root order).

Example 3

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

 Input: 
 Binary Tree:
          5
         / \
        3   8
         \
          4
 Target Node: 8
 
 Output: [5]
 
 Explanation:
 The ancestor of node 8 is just one node—5 (its parent).

Solution

Method 1 - Using DFS

Reasoning / Intuition

  1. Recursive DFS Traversal: To find the ancestors, traverse the binary tree using Depth First Search (DFS). Start from the root node, and explore its left and right subtrees, looking for the target node.
  2. Tracking Path: When the target node is found, backtrack by storing all nodes encountered during the recursion that led to the target node.
  3. Stopping Condition: Stop when the target node is reached, and return the path of nodes traversed up to this point.

Approach

  1. Perform a recursive traversal of the binary tree.
  2. At each node, recursively explore the left or right subtrees to check if the target node exists in those subtrees.
  3. If the target node is found in one of the subtrees, add the current node (ancestor) to the result list.
  4. Return the result list.

Code

 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

class Solution {
    public List<Integer> printAncestors(TreeNode root, int target) {
        // List to store ancestors
        List<Integer> ancestors = new ArrayList<>();
        
        // Helper function for recursive traversal
        boolean findAncestors(TreeNode node, int target, List<Integer> ancestors) {
            // Base case: if node is null
            if (node == null) {
                return false;
            }
            
            // Check if current node is the target
            if (node.val == target) {
                return true;
            }
            
            // Recursively search in left and right subtrees
            if (findAncestors(node.left, target, ancestors) || findAncestors(node.right, target, ancestors)) {
                // Add current node (ancestor) to the list
                ancestors.add(node.val);
                return true;
            }
            
            return false;
        }
        
        // Start DFS to find ancestors of the target node
        findAncestors(root, target, ancestors);
        return ancestors;
    }
}
 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 printAncestors(self, root, target):
        def findAncestors(node, target, ancestors):
            # Base case: If node is None
            if not node:
                return False
            
            # Check if the current node is the target
            if node.val == target:
                return True
            
            # Recursively check the left and right subtree
            if findAncestors(node.left, target, ancestors) or findAncestors(node.right, target, ancestors):
                # Add current node (ancestor) to the list
                ancestors.append(node.val)
                return True
            
            return False
        
        # List to store ancestors
        ancestors = []
        # Start DFS to find ancestors of the target node
        findAncestors(root, target, ancestors)
        return ancestors

Complexity

  • ⏰ Time complexity: O(n). We traverse all nodes in the tree in the worst case when the target node is a leaf node.
  • 🧺 Space complexity: O(h). The space complexity is determined by the depth of the tree h due to recursive calls (stack frames). In the case of a skewed tree, h = n, making worst-case space complexity O(n).