Zero To DSAZero To DSA
Privacy Policy
Validate Binary Search TreeSerialize and Deserialize Binary Tree

Lowest Common Ancestor of BST

medium
Time: O(h)
Space: O(1)

Given a BST, find the lowest common ancestor of two given nodes.

Constraints

  • All values are unique.
  • p and q exist in the tree.

Examples

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