Diwali Offer!Flat 20% OFF
Enroll Now
PrakalpanaLive online tech training

127. Lowest Common Ancestor of a Binary Search Tree

MediumDay 37 of 60Trees & BST

Given a binary search tree and two of its nodes p and q, return their lowest common ancestor: the deepest node that has both p and q in its subtree. A node counts as a descendant of itself, so if p is an ancestor of q, the answer is p. All values are unique and both nodes exist in the tree.

Example 1
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
2 is in the left subtree of 6 and 8 is in the right subtree, so they split at 6.
Example 2
Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
Output: 2
4 is inside the subtree of 2, and a node is its own ancestor.
Constraints
  • 2 <= number of nodes <= 10^5
  • -10^9 <= Node.val <= 10^9
  • All values are unique
  • p != q and both are in the tree
Hints
Frequently asked at: Amazon, Meta, Microsoft, LinkedIn
Ctrl + Enter runs the examples

Not sure what to learn next?

A 1-on-1 session with an industry mentor and a roadmap built for you. How it works

  1. 1Discuss your goals
  2. 2Get a personal plan
  3. 3Start learning
Book for β‚Ή200/ 30 min