Java Program to Find Lowest Common Ancestor

To find the lowest common ancestor in Java, use a recursive method that checks if the current node matches either target node or recursively searches left and right subtrees, returning the node where both targets split, like lowestCommonAncestor(root, p, q).

Examples

InputTree: [3,5,1,6,2,0,8,null,null,7,4], p=5, q=1

Output3

InputTree: [3,5,1,6,2,0,8,null,null,7,4], p=5, q=4

Output5

InputTree: [1,2], p=1, q=2

Output1

How to Think About It

To find the lowest common ancestor, start at the root and check if it matches either of the two nodes. If yes, return it. Otherwise, search the left and right subtrees. If both sides return a node, the current root is the lowest common ancestor. If only one side returns a node, propagate that node up.

Algorithm

1

Start at the root node.

2

If the root is null, return null.

3

If the root matches either target node, return root.

4

Recursively search the left subtree for the targets.

5

Recursively search the right subtree for the targets.

6

If both left and right recursive calls return non-null, return root as LCA.

7

Otherwise, return the non-null result from left or right.

Code

java

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

public class LCAFinder {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left != null && right != null) return root;
        return left != null ? left : right;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);

        LCAFinder finder = new LCAFinder();
        TreeNode lca = finder.lowestCommonAncestor(root, root.left, root.right);
        System.out.println(lca.val); // Output: 3
    }
}

Output

3

Dry Run

Let's trace the example where root=3, p=5, q=1 through the code.

1

Start at root

root=3, p=5, q=1; root is not null and not equal to p or q.

2

Search left subtree

Call lowestCommonAncestor on root.left=5.

3

Left subtree matches p

root=5 equals p=5, return node 5.

4

Search right subtree

Call lowestCommonAncestor on root.right=1.

5

Right subtree matches q

root=1 equals q=1, return node 1.

6

Both sides returned nodes

left=5, right=1, so return root=3 as LCA.

Call	root.val	left result	right result	Return
lowestCommonAncestor(3,5,1)	3	5	1	3
lowestCommonAncestor(5,5,1)	5	null	null	5
lowestCommonAncestor(1,5,1)	1	null	null	1

Why This Works

Step 1: Check base cases

If the current node is null or matches one of the targets, return it immediately to signal a found node.

Step 2: Search left and right

Recursively search both left and right children to find the targets in subtrees.

Step 3: Determine LCA

If both left and right return non-null, current node is where paths to p and q split, so it's the LCA.

Step 4: Propagate found node

If only one side returns a node, propagate it up as the potential ancestor.

Alternative Approaches

Parent Pointer Map

java

import java.util.*;

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

public class LCAFinder {
    Map<TreeNode, TreeNode> parentMap = new HashMap<>();

    public void buildParentMap(TreeNode root, TreeNode parent) {
        if (root != null) {
            parentMap.put(root, parent);
            buildParentMap(root.left, root);
            buildParentMap(root.right, root);
        }
    }

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        buildParentMap(root, null);
        Set<TreeNode> ancestors = new HashSet<>();
        while (p != null) {
            ancestors.add(p);
            p = parentMap.get(p);
        }
        while (q != null) {
            if (ancestors.contains(q)) return q;
            q = parentMap.get(q);
        }
        return null;
    }
}

Uses extra memory to store parents; useful if multiple LCA queries are needed.

Iterative Approach with Stack

java

import java.util.*;

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

public class LCAFinder {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Deque<TreeNode> stack = new ArrayDeque<>();
        Map<TreeNode, TreeNode> parent = new HashMap<>();
        parent.put(root, null);
        stack.push(root);
        while (!parent.containsKey(p) || !parent.containsKey(q)) {
            TreeNode node = stack.pop();
            if (node.left != null) {
                parent.put(node.left, node);
                stack.push(node.left);
            }
            if (node.right != null) {
                parent.put(node.right, node);
                stack.push(node.right);
            }
        }
        Set<TreeNode> ancestors = new HashSet<>();
        while (p != null) {
            ancestors.add(p);
            p = parent.get(p);
        }
        while (!ancestors.contains(q)) {
            q = parent.get(q);
        }
        return q;
    }
}

Iterative method avoids recursion but uses extra memory for parent map and stack.

Complexity: O(n) time, O(h) space

Time Complexity

The algorithm visits each node once, so it runs in O(n) time where n is the number of nodes.

Space Complexity

The recursion stack can go as deep as the tree height h, so space is O(h).

Which Approach is Fastest?

The recursive method is simple and efficient for one query; parent map methods use extra space but speed up multiple queries.

Approach	Time	Space	Best For
Recursive	O(n)	O(h)	Single LCA query, simple code
Parent Pointer Map	O(n)	O(n)	Multiple LCA queries, faster repeated lookups
Iterative with Stack	O(n)	O(n)	Avoid recursion, iterative environments