Lowest Common Ancestor of a BST

Q: 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) .

Q: 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 search both subtrees of every node and the work is O(n) . In a search tree, comparing the two values with a node tells you which side holds each of them, so you follow one path from the root. The recursive any-tree method still works on a search tree, but it throws that information away.

Q: 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 . The same rule gives p when the two values are equal. The walk handles both cases: it stops as soon as the current node equals one of the values.

Q: Why does the walk stop at the first node where p and q split?

At that node one value is smaller and the other larger, so they live in different subtrees. Any node below it lies in only one of those subtrees and cannot hold both. The split node holds both and nothing deeper does, which is exactly the definition of the lowest common ancestor.

MediumBinary search tree

+10

You get a binary search tree stored in the array tree in level order, and two values p and q that both appear in it. The root sits at index 0, the children of the node at index i sit at 2*i+1 (left) and 2*i+2 (right), -1 marks an empty spot, and the array may end with extra -1 entries. In a binary search tree, 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 a function named lowestCommonAncestor that returns the value of the lowest common ancestor of p and q: the deepest node that has both of them in its subtree. A node counts as part of its own subtree, so if p sits above q, the answer is p itself.

Function

lowestCommonAncestor(tree: integer-array, p: integer, q: integer) → integer

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 -1 or a value with 0 ≤ tree[i] ≤ 10⁵.
tree[0] is never -1, so the tree has at least one node.
The array may end with extra -1 entries 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.
p and q are 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: The 3 is the left child of 8, and the 15 hangs below 12 on the right of 8. Climbing up from each of them, the first node both reach is 8, so that is the answer; the root 20 is a common ancestor too, but a higher one.

Input: tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]p = 12q = 10
Output: 12
Explanation: The 10 is the left child of 12. A node counts as its own ancestor, so 12 has both values in its subtree and nothing below it does: the answer is 12. The values come in either order; here p is the larger one.

Input: tree = [50, 30, 70, 20, 40, 60, 80, -1, -1, -1, -1, 55]p = 55q = 80
Output: 70
Explanation: Both 55 and 80 are larger than the root 50, so they both live on its right. At 70 they part ways: 55 is smaller and sits on the left (below 60), 80 is larger and sits on the right. So 70 is the answer.

+12 hidden tests on Submit

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.

0 of 3 opened

Solution

In an ordinary binary tree you cannot tell where a value lives without searching both sides of every node. A search tree tells you at each node: smaller values are on the left, larger ones on the right. So start at the root and step toward the side that holds both values. The first node where they stop being on the same side is the answer, and you find it by following one path, never looking at the rest of the tree.

Search the whole tree, ignoring the order

Intuition

First, how to move around the array. The node at index i has its left child at 2*i+1 and its right child at 2*i+2. A child is real only if its index is inside the array and the value there is not -1. In [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15], the root 20 has 8 and 31 at indexes 1 and 2, and the 12 at index 4 has 10 and 15 at indexes 9 and 10.

This first method works on any binary tree. A recursive find(i) reports what the subtree at i contains. An empty spot reports -1. A node holding p or q reports itself: either the other value is below it, and then it is the answer, or the other value is elsewhere, and a node higher up will see both. Otherwise the node asks both children. If both sides report something, p is on one side and q on the other, so this node is where they meet. If only one side reports something, pass that up.

For p = 3 and q = 15, the 8 gets index 3 from its left and index 10 from its right, so it reports itself. The root gets that from its left and -1 from its right, and passes the 8 up.

It is correct, but it may visit every node, O(n) time, with O(h) for the recursion. It never uses the order of the values, which is the whole point of a search tree.

Algorithm

Write find(i). If the spot at i is empty (past the end or -1), return -1.
If tree[i] is p or q, return i.
Call find on 2*i+1 and 2*i+2. If both found something, return i.
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

Now use the order. You can find a value the way a search tree is meant to be searched: start at the root, go left when the value is smaller than the node, right when it is larger, and stop when you hit it. That walk passes through every ancestor of the value and nothing else, because the path from the root to a node is unique.

Record the walk for p and the walk for q. Both start at the root and follow the same nodes until the values go different ways. The shared beginning is the list of their common ancestors, so the last shared value is the lowest one. For 3 and 15 the paths are 20, 8, 3 and 20, 8, 12, 15: they share 20, 8, and the answer is 8. For 12 and 10 they are 20, 8, 12 and 20, 8, 12, 10, and the answer is 12.

Each walk takes one step per level, so the time is O(h), at most 14 steps here however many nodes the tree holds. The two lists take O(h) space.

Algorithm

Write path(target): start at index 0, record tree[i], stop when it equals target, otherwise move to 2*i+1 if target is smaller and to 2*i+2 if it is larger.
Build the path to p and the path to q.
Walk both lists from the start while their values match, remembering the last match.
Return that last shared value.

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 answer

Walk down until the values split

Intuition

The two paths agree for as long as p and q step in the same direction, so you do not need to store them. Walk both at once. At a node holding v, if both values are smaller than v, both live in the left subtree, and so does every common ancestor below v: go left. If both are larger, go right.

Otherwise you have arrived. Either one value is smaller than v and the other larger, so they sit in different subtrees and no child of v holds both; or one of them equals v, and a node is its own ancestor. Either way v is the deepest node above both.

In the third example the root 50 is below both 55 and 80, so you go right to 70. There 55 is smaller and 80 larger: the answer is 70. In the second example you go from 20 to 8 to 12, which equals p, and stop.

You follow a single path from the root, one comparison pair per level, so the time is O(h) and the space is O(1). The rest of the tree is never read.

Algorithm

Start at index i = 0.
Read v = tree[i].
If p < v and q < v, move to 2*i+1 and repeat.
If p > v and q > v, move to 2*i+2 and 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

The walk is short, so most bugs come from its stopping rule.

Using ≤ and ≥ in the move tests. With p = 12 and q = 10, the test p ≤ 12 and q ≤ 12 steps past the answer to 10, and from there the walk returns 10 or runs off the tree. Move only when both values are strictly on one side.
Assuming p < q. The values come in any order. Test both of them against the node, or swap them first so that p is the smaller.
Forgetting that one value can be the ancestor of the other. Then the answer is that value itself, not its parent.
Returning the index instead of the value. The function returns tree[i], not i.
Searching the whole tree. It gives the right answer, but it visits up to every node where one path is enough.
Mixing up the offset in Lua and R, where arrays start at 1. Keep the node indexes 0-based for the 2*i+1 arithmetic and read tree[i + 1].

Frequently asked questions4

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 search both subtrees of every node and the work is O(n). In a search tree, comparing the two values with a node tells you which side holds each of them, so you follow one path from the root. The recursive any-tree method still works on a search tree, but it throws that information away.

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. The same rule gives p when the two values are equal. The walk handles both cases: it stops as soon as the current node equals one of the values.

Why does the walk stop at the first node where p and q split?

At that node one value is smaller and the other larger, so they live in different subtrees. Any node below it lies in only one of those subtrees and cannot hold both. The split node holds both and nothing deeper does, which is exactly the definition of the lowest common ancestor.

Python

def lowestCommonAncestor(tree, p, q):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

tree = [20, 8, 31, 3, 12, 25, 40, -1, -1, 10, 15]
p = 3
q = 15

Expected

Lowest Common Ancestor of a BST

Function

Constraints

Examples

Hints

Solution

Search the whole tree, ignoring the order

Compare the two search paths

Walk down until the values split

Pitfalls and edge cases

Frequently asked questions4

Similar problems