Lowest Common Ancestor (LCA) of binary tree in java

ghz 10months ago ⋅ 100 views

To find the Lowest Common Ancestor (LCA) of two nodes in a binary tree in Java, you can follow these steps:

  1. Start from the root node.
  2. Traverse the tree recursively.
  3. If the current node is null or matches either of the given nodes, return the current node.
  4. Recur for the left and right subtrees.
  5. If both recursion calls return non-null values (i.e., both nodes are found in different subtrees), then the current node is the LCA.
  6. If only one recursion call returns a non-null value, return that value (either the LCA if found or one of the given nodes).
  7. If both recursion calls return null, neither of the given nodes exists in the tree, so return null.

Here's the Java code to implement this algorithm:

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

    public TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

public class LowestCommonAncestorBinaryTree {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // Base case: if root is null or matches either of the given nodes, return root
        if (root == null || root == p || root == q) {
            return root;
        }

        // Recur for left and right subtrees
        TreeNode leftLCA = lowestCommonAncestor(root.left, p, q);
        TreeNode rightLCA = lowestCommonAncestor(root.right, p, q);

        // If both left and right subtrees return non-null values, the current node is the LCA
        if (leftLCA != null && rightLCA != null) {
            return root;
        }

        // If only one subtree returns a non-null value, return that value
        return (leftLCA != null) ? leftLCA : rightLCA;
    }

    public static void main(String[] args) {
        // Create a sample binary tree
        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);

        LowestCommonAncestorBinaryTree lcaFinder = new LowestCommonAncestorBinaryTree();
        // Nodes to find LCA for
        TreeNode p = root.left; // Node with value 5
        TreeNode q = root.right; // Node with value 1

        TreeNode lca = lcaFinder.lowestCommonAncestor(root, p, q);
        System.out.println("Lowest Common Ancestor of " + p.val + " and " + q.val + " is: " + lca.val);
    }
}

In this implementation:

  • The lowestCommonAncestor method takes the root node of the binary tree, along with two nodes p and q, and returns their lowest common ancestor.
  • The method recursively traverses the tree, following the steps outlined above.
  • In the main method, a sample binary tree is created, and then the lowest common ancestor of two nodes p and q is found and printed.
#algorithm