Find Lowest Common Ancestor

Problem Explanation

The Lowest Common Ancestor (LCA) of two nodes in a binary tree is the deepest (lowest) node that has both nodes as descendants. In other words, it is the lowest node in the tree that is an ancestor of both given nodes.

Approach Name: Recursive

Approach to Solve the Problem

To find the LCA, we can use a recursive approach:

Base Case: If the current node is null, return null. If the current node is one of the two nodes, return the current node.
Recursive Case: Recursively find the LCA in the left and right subtrees.
Combining Results: If both left and right recursive calls return non-null values, the current node is the LCA. If only one returns a non-null value, return the non-null value.

java

python

​x
 
class TreeNode {    int val;    TreeNode left, right;​    TreeNode(int x) {        val = x;        left = right = null;    }}​public class TreeQues {    public TreeNode findLCA(TreeNode root, int a, int b) {        if (root == null || root.val == a || root.val == b) {            return root;        }        TreeNode left = findLCA(root.left, a, b);        TreeNode right = findLCA(root.right, a, b);​        if (left == null && right == null) {            return null;        }​        if (left != null && right != null) {            return root;        }​        return left != null ? left : right;    }​    public static void main(String[] args) {        // Building the tree        TreeNode root = new TreeNode(25);        root.left = new TreeNode(20);        root.right = new TreeNode(30);        root.left.left = new TreeNode(10);        root.left.right = new TreeNode(23);        root.left.left.left = new TreeNode(5);        root.left.right.right = new TreeNode(21);        root.right.right = new TreeNode(35);        root.right.right.left = new TreeNode(32);​        TreeQues treeQues = new TreeQues();​        // Finding LCA        int a = 5;        int b = 21;        TreeNode lcaNode = treeQues.findLCA(root, a, b);        System.out.println("LCA(" + a + ", " + b + "): " + (lcaNode != null ? lcaNode.val :                                                             "null"));​        a = 10;        b = 32;        lcaNode = treeQues.findLCA(root, a, b);        System.out.println("LCA(" + a + ", " + b + "): " + (lcaNode != null ? lcaNode.val :                                                             "null"));​        a = 21;        b = 32;        lcaNode = treeQues.findLCA(root, a, b);        System.out.println("LCA(" + a + ", " + b + "): " + (lcaNode != null ? lcaNode.val :                                                             "null"));    }}

Output:

LCA(5, 21): 20
LCA(10, 32): 25
LCA(21, 32): 25

Find Lowest Common Ancestor

Problem Explanation

Approach Name: Recursive

Approach to Solve the Problem

Java Tutorial

Python Tutorial