MediumTrees

Lowest Common Ancestor of a Binary Tree

treerecursiondfs

Problem

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

The LCA is defined as the lowest node that has both p and q as descendants.

Examples

Example 1

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p=5, q=1

Output: 3

Explanation: LCA of 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: 5 is an ancestor of 4.

Constraints

•All Node.val are unique.
•p != q
•p and q will exist in the tree.

Hints

Hint 1

Recurse: if current node is p or q, return it. LCA is where results from left and right are both non-null.

Solutions

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 both sides found a node, current root is the LCA
    if (left != null && right != null) return root;
    return left != null ? left : right;
}

Java

Time: O(n) · Space: O(h)