Lowest Common Ancestor of a Binary Tree
You get a binary tree in the array root, in heap order: the root at index 0, the children of index i at 2*i+1 (left) and 2*i+2 (right), and -1 for an empty spot. The values are distinct and follow no order.
Return the value of the lowest common ancestor of p and q, the values of two different nodes: the deepest node whose subtree holds both. A subtree includes its top node, so if q lies below p, the answer is p.
Function
- rootinteger-array
- the binary tree in level order, with -1 for an empty spot
- pinteger
- the value of one node
- qinteger
- the value of another node
- Returnsinteger
- the value of the lowest node whose subtree holds both p and q
Constraints
2 ≤ root.length ≤ 32767- Each
root[i]is-1or a value with0 ≤ root[i] ≤ 104. root[0]is never-1, and the tree has at least two nodes.- 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. - All values in the tree are distinct, and they follow no order.
pandqare the values of two different nodes in the tree, in any order.
Examples
- Input
- root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 6q = 9
- Output
- 3
- Explanation
6is the left child of3, and9sits below4on the right of3, so they meet at3. Comparing values would point at the root8:6is smaller and9larger.
- Input
- root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9]p = 4q = 7
- Output
- 4
- Explanation
7is the left child of4, and the subtree of4includes4itself, so the answer is4.
- Input
- root = [1, -1, 6, -1, -1, 3, 0, -1, -1, -1, -1, -1, -1, -1, -1]p = 3q = 0
- Output
- 6
- Explanation
- The root
1has no left child. Its right child6has3on its left and0on its right, so the values meet at6.
Follow-up
If p or q may be absent, with -1 as the answer, which shortcut in the single pass breaks, and how do you still finish in one traversal?
Hints
Open them one at a time. Each one gives away a little more.
Try the search-tree rule on the first example:
6is smaller than the root8and9is larger. Where do they really sit? What does that say about comparing values in this tree?Let every subtree tell its parent what it found: nothing, one of the two values, or the answer. A node that hears about a value from both of its children is where
pandqmeet.Write a recursive
find(i)that returns-1for an empty spot,iwhenroot[i]isporq,iwhen both children return an index, and otherwise the child result that is not-1. The answer isroot[find(0)].
Solution
No order tells you which side holds a value, so you have to look. One post-order pass lets every subtree report what it found, and the values meet at the first node that hears from both sides.
Walk down, searching each side
Intuition
Walk down from the root, and at each node search the left subtree for p and for q. Both there: go left. Neither: go right. One each: the values split, and this node is the answer. A node holding p or q is the answer too, since the other value must sit below it. For 6 and 9, the root finds both on its left, and at 3 the lone 6 holds only p.
Every step down searches a whole subtree, so h levels cost O(n·h), and O(n²) on a tall, narrow tree with no depth limit. The search at 8 already visited every node below 3, and the step at 3 visits some again.
Algorithm
- Write
contains(i, value):falsefor an empty spot (past the end or-1),trueifroot[i]equalsvalue, otherwise ask both children. - Start at
i = 0. Ifroot[i]isporq, return it. - If the left subtree at
2*i+1holds both values, move there. If it holds neither, move to2*i+2. - Otherwise return
root[i].
def lowestCommonAncestor(root, p, q):
n = len(root)
def contains(i, value):
# Is value somewhere in the subtree at index i?
if i >= n or root[i] == -1:
return False
if root[i] == value:
return True
return contains(2 * i + 1, value) or contains(2 * i + 2, value)
i = 0 # p and q are always inside the subtree at i
while True:
if root[i] == p or root[i] == q:
return root[i] # one value is here, the other is below it
left = 2 * i + 1
p_left = contains(left, p)
q_left = contains(left, q)
if p_left and q_left:
i = left # both on the left
elif not p_left and not q_left:
i = 2 * i + 2 # both on the right
else:
return root[i] # one on each sideOne post-order pass
Intuition
Let every subtree answer once, from the bottom up. find(i) returns the answer's index if the subtree at i holds both values, the index of p or q if it holds one, and -1 if it holds neither.
A node holding p or q returns its own index without looking below. If the other value is in its subtree, this node is the answer; if not, a node higher up hears from both sides. Any other node asks both children. Two results mean the values came up different sides and meet here. A single result passes up unchanged, whether it is one value or the finished answer.
In the first example, 3 gets index 3 from its left and 10 from its right, returns its own index 1, and the root passes it up. Each node is visited once: O(n) time, O(h) recursion.
Algorithm
find(i)gives-1for an index past the end or a-1.- A node whose value is
porqgivesiwithout looking below. - Any other node computes
left = find(2*i+1)andright = find(2*i+2). If neither is-1, it givesi; otherwise the one that is not-1, or-1. - Return
root[find(0)].
def lowestCommonAncestor(root, p, q):
n = len(root)
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 root[i] == -1:
return -1
if root[i] == p or root[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 root[find(0)]
Pitfalls and edge cases
- Comparing values with the node. The tree has no order: in the first example that walk stops at the root
8instead of3. - Passing up
trueorfalseinstead of an index. The parent cannot tell whether the finished answer is already below it. - Reading a child without checking the length. The
9at index10has child indexes21and22, past the last entry. - Returning
find(0), an index, instead ofroot[find(0)]. - In Lua and R, arrays start at 1: keep node indexes 0-based and read
root[i + 1].
Frequently asked questions3
What is the time complexity of the lowest common ancestor of a binary tree?
The post-order pass enters each node at most once: O(n) time. The recursion stack holds one frame per level, so the space is O(log n) on a balanced tree and O(n) on a tree shaped like a path.
How is this different from the lowest common ancestor in a binary search tree?
In a search tree, comparing p and q with a node tells you which side holds each, so one path from the root finds the answer in O(h). Here a comparison says nothing, so you search the subtrees.
Can you find the lowest common ancestor with parent pointers?
Yes. In this array the parent of index i is (i-1)/2 rounded down. Move the larger of the two indexes to its parent until they are equal; a larger index is never an ancestor of a smaller one. With linked nodes, put the ancestors of p in a set and climb from q to the first one in it.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def lowestCommonAncestor(root, p, q):
# Write code hereTest #1
Test #2
Test #3
Arguments
root = [8, 3, 10, 6, 4, 12, 1, -1, -1, 7, 9] p = 6 q = 9
Expected Output
3