Skip to main content
Back to ChallengesLowest Common AncestorMedium 30 min

Lowest Common Ancestor

Given a binary tree and two nodes **p** and **q**, find their **Lowest Common Ancestor (LCA)**.

The LCA is defined as the lowest node in the tree that has both p and q as descendants (a node can be a descendant of itself).

Examples

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

Constraints

  • • Number of nodes in [2, 10^5]
  • • -10^9 <= Node.val <= 10^9
  • • All Node.val are unique
  • • p != q, both exist in the tree

Complexity Analysis

Time
O(n)
potentially visit all nodes.
Space
O(h)
recursion stack.

Test Cases

#1 LCA is root
Input: [3,5,1,6,2,0,8,null,null,7,4] p=5 q=1
Expected: 3
#2 One is ancestor of other
Input: [3,5,1,6,2,0,8,null,null,7,4] p=5 q=4
Expected: 5
#3 Root and child
Input: [1,2] p=1 q=2
Expected: 1
JavaScript
Output
Click "Run Code" to see output here...