186. Lowest Common Ancestor of a Binary Search Tree

MediumBST

Given a binary search tree (BST), find the lowest common ancestor (LCA) node of two given nodes in the BST. 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).

Examples

Input: [6,2,8,0,4,7,9,null,null,3,5] 2 8

Output: 6

Explanation: 2 < 6 and 8 > 6, so they split at the root: the LCA is 6.

Constraints

  • The number of nodes in the tree is in the range [2, 10^5].
  • -10^9 <= Node.val <= 10^9
  • All Node.val are unique.
  • p != q
  • p and q will exist in the BST.
Loading...

Run checks all cases above. Submit evaluates all test cases.