Lowest Common Ancestor of a BST
You get a binary search tree stored in heap order in the array tree: the root is at index 0, the children of index i are at 2*i+1 (left) and 2*i+2 (right), and -1 marks an empty spot. Every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger.
Write lowestCommonAncestor, which returns the value of the lowest common ancestor of the values p and q, both in the tree: the deepest node that has both in its subtree. A node is part of its own subtree, so if p sits above q, the answer is p.
Function
- treeinteger-array
- the binary search tree in level order, with -1 for an empty spot
- pinteger
- the first value to find
- qinteger
- the second value to find
- Returnsinteger
- the value of the deepest node that has both p and q in its subtree
Constraints
1 ≤ tree.length ≤ 32767- Each
tree[i]is-1or a value with0 ≤ tree[i] ≤ 105. tree[0]is never-1, so the tree has at least one node.- The array may end with extra
-1entries past the last node. - Both children of an empty spot are empty too, and the depth is at most
14. - The tree is a valid binary search tree, so all its values are distinct.
pandqare values of nodes in the tree. They come in any order and may be equal.
Examples
- Input
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 3q = 15
- Output
- 8
- Explanation
- Climbing from
3and from15, the first node both reach is8:3is its left child and15hangs below12on its right. The root20is a common ancestor too, but higher.
- Input
- tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
- Output
- 12
- Explanation
10is the left child of12, and a node counts as its own ancestor, so12holds both values and nothing below it does. Herepis the larger value.
- Input
- tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
- Output
- 70
- Explanation
- Both values are larger than the root
50, so both live on its right. At70they part:55is smaller and sits on the left, below60, and80is larger.
Follow-up
What would you change if p or q might be missing from the tree, and the function had to return -1 in that case?
Hints
Open them one at a time. Each one gives away a little more.
Stand at the root. If both
pandqare smaller than its value, in which subtree are both nodes?As long as both values are on the same side of the current node, every common ancestor deeper down is on that side too. The first node where they are not on the same side, or where the node holds one of them, is the one you want.
Start at index
0. While both values are smaller thantree[i], move to2*i+1; while both are larger, move to2*i+2. Otherwise returntree[i].
Solution
A search tree tells you at each node where a value lives: smaller on the left, larger on the right. Start at the root and step toward the side that holds both values. The first node where they stop sharing a side is the answer, and you reach it on one path.
Search the whole tree, ignoring the order
Intuition
This method works on any binary tree. A recursive find(i) reports what the subtree at i holds. A node holding p or q reports itself: if the other value is below it, it is the answer, and if not, a node higher up sees both. Any other node asks both children. If both report something, p and q sit on different sides and this node is where they meet; if one does, pass that up.
For 3 and 15, the 8 gets index 3 from its left and index 10 from its right and reports itself. It may visit every node: O(n) time, and O(h) for the recursion.
Algorithm
- Write
find(i). If the spot atiis empty (past the end or-1), return-1. - If
tree[i]isporq, returni. - Call
findon2*i+1and2*i+2. If both found something, returni. - Otherwise return whichever side found something, or
-1. - Return
tree[find(0)].
def lowestCommonAncestor(tree, p, q):
n = len(tree)
def find(i):
# In the subtree at index i: the index of the answer if both values are
# inside, the index of the one that is, or -1 when neither is.
if i >= n or tree[i] == -1:
return -1
if tree[i] == p or tree[i] == q:
return i
left = find(2 * i + 1)
right = find(2 * i + 2)
if left != -1 and right != -1:
return i # one value on each side: this node is the answer
return left if left != -1 else right
return tree[find(0)]Compare the two search paths
Intuition
Search for a value the usual way: from the root, go left when it is smaller than the node and right when it is larger. The path from the root to a node is unique, so the walk passes every ancestor of the value and nothing else.
Record both walks. They share nodes until the values go different ways, so the shared beginning lists the common ancestors and its last value is the lowest. For 3 and 15 the paths are 20, 8, 3 and 20, 8, 12, 15: they share 20, 8, so the answer is 8. Each walk takes one step per level: O(h) time, and O(h) space for the lists.
Algorithm
- Write
path(target): start at index0, recordtree[i], stop when it equalstarget, otherwise move to2*i+1iftargetis smaller and to2*i+2if it is larger. - Build the path to
pand the path toq. - Walk both lists from the start and return the last value they share.
def lowestCommonAncestor(tree, p, q):
def path(target):
# The values met on the way from the root down to target.
values = []
i = 0
while True:
values.append(tree[i])
if tree[i] == target:
return values
i = 2 * i + 1 if target < tree[i] else 2 * i + 2
to_p, to_q = path(p), path(q)
# Both paths start at the root; the answer is the last value they share.
answer = to_p[0]
for a, b in zip(to_p, to_q):
if a != b:
break
answer = a
return answerWalk down until the values split
Intuition
The two paths agree while p and q step the same way, so walk both at once. At a node holding v, if both values are smaller, both live in the left subtree, and so does every common ancestor below v: go left. If both are larger, go right.
Otherwise one value is smaller and the other larger, so no child of v holds both, or one of them equals v, which is its own ancestor. Either way v is the deepest node above both. In the third example, 50 is below both values, so you go right to 70, where 55 is smaller and 80 larger. One comparison pair per level gives O(h) time and O(1) space.
Algorithm
- Start at index
i = 0. - Read
v = tree[i]. - If
p < vandq < v, move to2*i+1and repeat. - If
p > vandq > v, move to2*i+2and repeat. - Otherwise return
v.
def lowestCommonAncestor(tree, p, q):
i = 0 # start at the root
while True:
value = tree[i]
if p < value and q < value:
i = 2 * i + 1 # both are smaller: the answer is on the left
elif p > value and q > value:
i = 2 * i + 2 # both are larger: the answer is on the right
else:
return value # they split here, or one of them is this node
Pitfalls and edge cases
- Using
≤and≥in the move tests. Withp = 12andq = 10, the walk steps past12to10, then returns10or runs off the tree. - Assuming
p < q. In the second examplepis the larger value. Test both against the node, or swap them first. - Returning the index instead of the value. The answer is
tree[i], noti. - In Lua and R, arrays start at 1. Keep node indexes 0-based for the
2*i+1arithmetic and readtree[i + 1].
Frequently asked questions3
What is the time complexity of the lowest common ancestor in a BST?
The walk from the root follows one path, so it takes O(h) time for a tree of depth h and O(1) extra space. On a balanced tree that is O(log n); on a tree shaped like a single path it is O(n).
How is the LCA in a binary search tree different from the LCA in a binary tree?
In an ordinary binary tree a value can be anywhere, so you may search every node, O(n) work. In a search tree, comparing the two values with a node tells you which side holds each, so you follow one path from the root.
Can a node be its own lowest common ancestor?
Yes. A node counts as an ancestor of itself, so when p sits above q the answer is p, and when the two values are equal the answer is that value.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def lowestCommonAncestor(tree, p, q):
# Write code hereTest #1
Test #2
Test #3
Arguments
tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15] p = 3 q = 15
Expected Output
8