Lowest Common Ancestor of a Binary Tree medium

Problem Statement

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

A node can be a descendant of itself according to this definition.

Example 1

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

Example 2

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
Output: 5
Explanation: The LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Steps

1. Recursive Approach: We'll use a recursive function to traverse the tree.
2. Base Cases:
   • If the current node is null, return null.
   • If the current node is either p or q, return the current node.
3. Recursive Calls:
   • Recursively search the left and right subtrees.
4. Result Combination:
   • If both left and right subtrees return non-null values, it means that p and q are on different branches, and the current node is their LCA. Return the current node.
   • Otherwise, return the non-null result from either the left or right subtree (the one that contains both p and q).

Explanation

The algorithm efficiently finds the LCA because it systematically explores the tree. If both p and q are found in different subtrees of a node, that node must be the LCA. If they are both found in the same subtree, the LCA must lie within that subtree, and the recursion continues. The base cases handle situations where either p or q is found or the end of a branch is reached.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    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;
        } else if (left != null) {
            return left;
        } else {
            return right;
        }
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the binary tree. In the worst case, we might have to traverse all nodes.
• Space Complexity: O(H), where H is the height of the binary tree. This is due to the recursive call stack. In the worst case (a skewed tree), H could be equal to N. In a balanced tree, H would be log(N).