Lowest Common Ancestor of a Binary Tree - Java Solution

1. Introduction

This blog post addresses a fundamental problem in binary tree algorithms: finding the lowest common ancestor (LCA) of two nodes. The LCA of two nodes p and q in a binary tree is defined as the lowest node that has both p and q as descendants (where a node can be a descendant of itself). This problem is essential in many applications, including computational biology and data structure optimization.

Problem

Given a binary tree and two of its nodes, p and q, the task is to find their lowest common ancestor. The LCA is the lowest node in the tree that has both p and q as its descendants.

2. Solution Steps

1. Use a recursive approach to traverse the tree.

2. If the current node is either p or q, return the current node.

3. Recursively search for p and q in the left and right subtrees.

4. If both subtrees return non-null values, the current node is the LCA.

5. If only one subtree returns a non-null value, propagate this value upwards.

6. Return the LCA node found.

3. Code Program

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}

public class LowestCommonAncestorBinaryTree {
    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);
        TreeNode p = root.left; // Node with value 5
        TreeNode q = root.right; // Node with value 1

        TreeNode lca = lowestCommonAncestor(root, p, q);
        System.out.println("LCA: " + (lca != null ? lca.val : "null")); // Test the function
    }

    // Function to find the lowest common ancestor in a binary tree
    public static 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;
    }
}

Output:

LCA: 3

Explanation:

1. lowestCommonAncestor: This function identifies the lowest common ancestor of two nodes in a binary tree.

2. The function checks if the current node is null or matches either of the target nodes (p or q). If so, it returns the current node.

3. It then recursively searches for p and q in the left and right subtrees.

4. If both the left and right subtree calls return non-null values, it means p and q are found in different subtrees, and the current node is their LCA.

5. If only one subtree call returns a non-null value, the LCA is further up the tree.

6. The function continues this process, propagating the findings upwards, until the LCA is identified.

7. The output prints the value of the LCA node found in the binary tree.