Lowest Common Ancestor in Java: Explanation & Practice

Problem summary

Given a binary tree and two nodes p and q, find their lowest common ancestor (LCA). LCA is the deepest node that has both p and q as descendants.

Starter code

public class Main {
    public static void main(String[] args) {
        // Tree:       3
        //           /   \
        //          5     1
        //         / \   / \
        //        6   2 0   8
        // LCA of 5 and 1 is 3
        // LCA of 5 and 4 is 5 (ancestor of itself)
        // Print: LCA: 3
    }
}

Expected output and test cases

• p=5, q=1

  LCA: 3

• p=5, q=4

  LCA: 5

• p=0, q=8

  LCA: 1

Hints

1. If current node is p or q, return it
2. Recursively search left and right subtrees
3. If both return non-null, current node is LCA
4. If only one returns non-null, return that one

Related Data Structures & Algorithms exercises

• Practice Binary Tree Level Order Traversal in Java
• Practice Validate Binary Search Tree in Java
• Practice Number of Islands in Java

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler