codejump
EasyPythonJavaScriptTypeScript

BST — Lowest Common Ancestor

Data StructuresTreesBinary Search Tree

solve(levelOrder, p, q) — in a binary search tree with unique values,
return the value of the lowest common ancestor of p and q. A node is a
descendant of itself, and both values are guaranteed to be in the tree.

Unlike a general binary tree, the ordering tells you where to go. **No
recursion is needed**: walk down from the root in O(h) time and O(1) space.

Examples (tree [6, 2, 8, 0, 4, 7, 9, null, null, 3, 5])

solve(tree, 2, 8)  → 6
solve(tree, 2, 4)  → 2
solve(tree, 3, 5)  → 4
solve(tree, 7, 9)  → 8

Sample tests

Test #1Values on both sides of the root
Input: [[6,2,8,0,4,7,9,null,null,3,5],2,8]
Output: 6
Test #2One value is the ancestor
Input: [[6,2,8,0,4,7,9,null,null,3,5],2,4]
Output: 2
Test #3Siblings
Input: [[6,2,8,0,4,7,9,null,null,3,5],3,5]
Output: 4
← All challenges