Lowest Common Ancestor in a BST
Updated
Problem statement
Given the root of a binary search tree and two node values p and q, return the value of their lowest common ancestor. An ancestor may be the queried node itself; the lowest common ancestor is the deepest node that is an ancestor of both.
For this exercise, assume all tree values are unique, both query values exist in the tree, and they may be equal. Every value in a node's left subtree is smaller, and every value in its right subtree is larger. The input tree is shown in level order, using null for missing children.
Function
lcaBstValue(root: TreeNode, p: int, q: int) → intExamples
Example 1
root = [10,5,15,2,7,12,20]p = 2q = 7return = 5Nodes 2 and 7 lie in different child subtrees of node 5. Their deepest shared ancestor is 5.
Example 2
root = [10,5,15,2,7,12,20]p = 5q = 7return = 5Node 5 is itself an ancestor of node 7, so it is the lowest common ancestor.
Constraints
- For this exercise, assume the tree contains 1 to 1000 nodes.
- Node values, p and q are integers from
-10^9through10^9. - The tree is a valid strict BST with unique values, and p and q are present.
More PeopleStrong Onsite Interview questions
- Add Two Binary StringsONSITE INTERVIEW · Seen Mar 2026
- Four SumONSITE INTERVIEW · Seen Mar 2026
- LRU Cache OperationsONSITE INTERVIEW · Seen Mar 2026
- Sliding Window MaximumONSITE INTERVIEW · Seen Mar 2026
- Find the Entry of a Linked List CycleONSITE INTERVIEW · Seen Sep 2025
- Integer to English Words: Up to 20 DigitsONSITE INTERVIEW · Seen Sep 2025
- Word Ladder II: All Shortest TransformationsONSITE INTERVIEW · Seen Sep 2025
- Detect a Cycle in a Linked ListONSITE INTERVIEW · Seen May 2025
- First Nonrepeating CharacterONSITE INTERVIEW · Seen May 2025
- Longest Subarray with a Target SumONSITE INTERVIEW · Seen May 2025
Similar questions at other companies
- Insert into a Left-Complete Binary TreeRubrik · ONSITE INTERVIEWRubrik interview questions
- Kth Closest Element in a BSTLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Shortest Path Between BST NodesGoogle · ONSITE INTERVIEWGoogle interview questions
- Repeated BST Range Sum and AverageMeta · ONSITE INTERVIEWMeta interview questions
- Delete Node in a BSTBloomberg LP · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Validate Binary Search TreeTokopedia · ONSITE INTERVIEWTokopedia interview questions
- Build a Perfect Binary Search TreeExpedia · ONSITE INTERVIEWExpedia interview questions
- Check the Order of a Binary Search TreeCapital One · ONSITE INTERVIEWCapital One interview questions
- Next Larger Value in a BSTMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Top K Pins with Insert and QueryPinterest · PHONE SCREENPinterest interview questions