Find the Ancestors of a Node in a BST

Given the root of a binary search tree and a target value, return the target's ancestors, from its parent up to the root. Return an empty Optional if the target is not in the tree. (The root has no ancestors, so it returns an empty list.)

Example

Text

Values inserted: 6, 4, 9, 2, 5, 8, 12, 10, 14
target 10 -> [12, 9, 6]
target 6  -> []        (the root)
target 7  -> empty     (not in the tree)

graph TB
    a["6"] --> b["4"]
    a --> c["9"]
    b --> d["2"]
    b --> e["5"]
    c --> f["8"]
    c --> g["12"]
    g --> h["10 (target)"]
    g --> i["14"]
    style a stroke-width:3px
    style c stroke-width:3px
    style g stroke-width:3px

Brute force: DFS with backtracking

Search the whole tree depth-first while keeping the current root-to-node path in an ArrayList:

Add a node's value before exploring its children.
If either child's subtree contains the target, stop, and the path holds the ancestors.
Otherwise, remove the last value before returning (backtrack), since this node is not on the path to the target.

This does not use the BST ordering, so it works for any binary tree.

A tree node is an object with an int val and two reference fields, left and right. A missing child is null. The fields are mutable, so no wrapper type is needed. Optional<List<Integer>> is a container that holds either a list or nothing.

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Optional;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    static TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = new TreeNode(val); break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = new TreeNode(val); break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static TreeNode fromValues(int... values) {
        TreeNode root = null;
        for (int v : values) root = insert(root, v);
        return root;
    }

    static boolean pathTo(TreeNode root, int target, List<Integer> path) {
        if (root == null) return false;
        if (root.val == target) return true;
        path.add(root.val);
        if (pathTo(root.left, target, path) || pathTo(root.right, target, path)) {
            return true;
        }
        path.remove(path.size() - 1); // not on the way to the target
        return false;
    }

    static Optional<List<Integer>> ancestors(TreeNode root, int target) {
        List<Integer> path = new ArrayList<>();
        if (!pathTo(root, target, path)) return Optional.empty();
        Collections.reverse(path); // nearest ancestor first
        return Optional.of(path);
    }

    public static void main(String[] args) {
        TreeNode root = fromValues(6, 4, 9, 2, 5, 8, 12, 10, 14);
        System.out.println(ancestors(root, 10) + " " + ancestors(root, 6) + " " + ancestors(root, 7));
    }
}

Output

Optional[[12, 9, 6]] Optional[[]] Optional.empty

Time: O(n): in the worst case the whole tree is searched. Space: O(h) for the path and the recursion.

Optimal: follow the search path

In a BST there is only one path from the root to any value, the path a search would take. Walk it from the root, recording each node you pass. If you reach the target, the recorded nodes are its ancestors.

Walkthrough with target 10:

node	compare	recorded so far	next
6	10 > 6	[6]	right
9	10 > 9	[6, 9]	right
12	10 < 12	[6, 9, 12]	left
10	found		return [12, 9, 6]

Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Optional;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    static TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = new TreeNode(val); break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = new TreeNode(val); break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static TreeNode fromValues(int... values) {
        TreeNode root = null;
        for (int v : values) root = insert(root, v);
        return root;
    }

    static Optional<List<Integer>> ancestors(TreeNode root, int target) {
        List<Integer> path = new ArrayList<>();
        TreeNode cur = root;
        while (cur != null) {
            if (cur.val == target) {
                Collections.reverse(path);
                return Optional.of(path);
            }
            path.add(cur.val);
            cur = target < cur.val ? cur.left : cur.right;
        }
        return Optional.empty(); // fell off the tree: not found
    }

    public static void main(String[] args) {
        TreeNode root = fromValues(6, 4, 9, 2, 5, 8, 12, 10, 14);
        System.out.println(ancestors(root, 10) + " " + ancestors(root, 6) + " " + ancestors(root, 7));
        System.out.println(ancestors(root, 5));
    }
}

Output

Optional[[12, 9, 6]] Optional[[]] Optional.empty
Optional[[4, 6]]

Time: O(h). Space: O(h) for the output, with no recursion.

Optional<List<Integer>> separates two answers that would look the same as a bare list: Optional[[]] means "found, and it is the root", and Optional.empty means "not in the tree".

The lowest common ancestor (LCA) of two values in a BST (LeetCode 235) is where their search paths split: walk down from the root while both values are on the same side of the current node.

Java

import java.util.OptionalInt;

public class Main {
    static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int val) { this.val = val; }
    }

    static TreeNode insert(TreeNode root, int val) {
        if (root == null) return new TreeNode(val);
        TreeNode cur = root;
        while (true) {
            if (val < cur.val) {
                if (cur.left == null) { cur.left = new TreeNode(val); break; }
                cur = cur.left;
            } else {
                if (cur.right == null) { cur.right = new TreeNode(val); break; }
                cur = cur.right;
            }
        }
        return root;
    }

    static TreeNode fromValues(int... values) {
        TreeNode root = null;
        for (int v : values) root = insert(root, v);
        return root;
    }

    static OptionalInt lca(TreeNode root, int a, int b) {
        TreeNode node = root;
        while (node != null) {
            if (a < node.val && b < node.val) {
                node = node.left;
            } else if (a > node.val && b > node.val) {
                node = node.right;
            } else {
                return OptionalInt.of(node.val); // the paths split here
            }
        }
        return OptionalInt.empty();
    }

    public static void main(String[] args) {
        TreeNode root = fromValues(6, 4, 9, 2, 5, 8, 12, 10, 14);
        System.out.println(lca(root, 10, 14) + " " + lca(root, 2, 8));
    }
}

Output

OptionalInt[12] OptionalInt[6]

Brute force: DFS with backtracking

Optimal: follow the search path

Related: lowest common ancestor