Practice
JavaScriptData StructuresReactConcepts
Sign in
← Back to problems

Lowest Common Ancestor of a BST

BSTmedium

A binary search tree node is `{ val, left, right }`. Implement `lca(root, p, q)` returning the value of the lowest node that is an ancestor of both values `p` and `q` (a node is an ancestor of itself). Use the BST ordering for an O(height) solution. (Asked at Microsoft and Amazon.)

Examples

Input: tree rooted at 6, p = 2, q = 8
Output: 6
2 is in the left subtree, 8 in the right, so they split at the root.
Input: tree rooted at 6, p = 2, q = 4
Output: 2
4 lives under 2, so 2 is their lowest common ancestor.

Sample tests

Input: lca({"val":6,"left":{"val":2,"left":{"val":0,"left":null,"right":null},"right":{"val":4,"left":{"val":3,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}}},"right":{"val":8,"left":{"val":7,"left":null,"right":null},"right":{"val":9,"left":null,"right":null}}}, 2, 8)
Output: 6
Input: lca({"val":6,"left":{"val":2,"left":{"val":0,"left":null,"right":null},"right":{"val":4,"left":{"val":3,"left":null,"right":null},"right":{"val":5,"left":null,"right":null}}},"right":{"val":8,"left":{"val":7,"left":null,"right":null},"right":{"val":9,"left":null,"right":null}}}, 2, 4)
Output: 2

+ 2 hidden tests run on Submit.

Hints

Common pitfalls
  • Ignoring the BST ordering and doing a general-tree LCA search is O(n) instead of O(height).
  • Forgetting that a node can be the ancestor of itself when p or q equals the current value.

Learning resources

  • Wikipedia: Lowest common ancestor
Approach & explanation (try first)

Descend from the root: while both values lie on the same side, move that way. The moment they diverge — or one matches the current node — that node is the lowest common ancestor. The walk costs O(height), which is O(log n) for a balanced BST.

Loading...
⌘/Ctrl + Enter

Run your code to see results.