Ancestors in Binary Tree

Time: O(n)

Space: O(h)

Intuition

Print all ancestors of a given node in binary tree. DFS that returns true when target found; nodes on return path are ancestors.

Algorithm

1Recursive DFS. If found in left or right subtree: print current node and return true.

Common Pitfalls

•Post-order DFS. Print node only after confirming target is in its subtree.

Ancestors in Binary Tree.java

Java

// Approach: DFS. Recursively search for the target node; on the way back up, print ancestors.
// Time: O(n) Space: O(h)
import java.util.*;

class Node {
    int data;
    Node left, right;

    Node(int key) {
        data = key;
        left = right = null;
    }
}

class Solution {

    public ArrayList<Integer> Ancestors(Node root, int target) {
        ArrayList<Integer> ans = new ArrayList<>();
        solve(root, target, ans);

        return ans;
    }

    private boolean solve(Node root, int target, ArrayList<Integer> ans) {
        if (root == null)
            return false;

        if (root.data == target)
            return true;

        boolean left = solve(root.left, target, ans);
        boolean right = solve(root.right, target, ans);

        if (left || right) {
            ans.add(root.data);
            return true;
        }

        return false;
    }
}

Was this solution helpful?