Back to DSA

Lowest Common Ancestor of a Binary Tree

medium
Acceptance: 53%
Binary Tree

In a binary tree (not necessarily a BST), find the lowest common ancestor of two specified nodes. The lowest common ancestor is the deepest node that is an ancestor of both target nodes. A node is considered an ancestor of itself.

Examples

Example 1:
Input:root = [10,5,15,3,7,12,20], p = 3, q = 7
Output:5
Example 2:
Input:root = [10,5,15,3,7,12,20], p = 5, q = 20
Output:10

Hints

Related Problems

Maximum Depth of Binary TreeeasyInvert Binary TreeeasyValidate Binary Search TreemediumBinary Tree Level Order TraversalmediumBinary Tree Zigzag Level Order Traversalmedium
00:00
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;
        return left != null ? left : right;
    }
}
Time complexityO(n)
Space complexityO(h)