Largest value shared by two BSTs: Frontier Interview's solution

Question: Largest value shared by two BSTs

Companies: Google, Amazon, Microsoft

Difficulty: Medium

Problem statement

You are given the roots of two binary search trees, a and b, holding integer values. Return the largest integer that appears in both trees. If the trees share no value, return -1.

Implement:

def largest_common_value(a: TreeNode | None, b: TreeNode | None) -> int: ...

where TreeNode has val, left and right.

Constraints

Each tree has between 1 and 10^5 nodes.
Every node value is between -10^9 and 10^9.
Both inputs are valid BSTs: every value in a node's left subtree is smaller than the node's value, and every value in its right subtree is larger.
Trees may be unbalanced, so the height can be as large as the node count.

Aim for better than O(n) extra memory by using the BST ordering.

Example 1

Tree a values: 1, 3, 6, 8, 10, 12, 15
Tree b values: 2, 4, 6, 7, 10, 11, 14
Output: 10

Both 6 and 10 appear in both trees. 10 is the larger one.

Example 2

Tree a values: 2, 5, 9
Tree b values: 1, 4, 7
Output: -1

No value appears in both trees.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

We want the biggest integer that appears in both BSTs, or -1 if none does.

Brute force. Put every value from tree A into a hash set, then walk tree B
and keep the largest value that is in the set. This is O(n + m) time and
O(n) extra space, and it ignores the BST property. It is a fine first answer
and a good baseline to state in one sentence.

Use the ordering. An in-order traversal of a BST yields its values in
sorted order; a reverse in-order traversal (right, node, left) yields them
in descending order. Treat each tree as a descending stream and merge the two
streams like the merge step of merge sort, but from the top:

If the two current values are equal, that value is in both trees, and since
both streams are descending it is the largest common value. Return it.
Otherwise the larger value cannot be common: everything left in the other
stream is smaller than or equal to the other current value, which is already
smaller. Advance the stream holding the larger value.
If either stream runs out, there is no common value: return -1.

Each stream is an iterator backed by an explicit stack. To produce the next
value, pop a node, then push its left child and that child's whole right
spine. This is the standard "BST iterator" in reverse.

Invariants.

Each stack holds exactly the nodes whose value and left subtree have not
been emitted yet, along one root-to-node path, so its size is at most the
tree height.
Every value already discarded from either stream is strictly greater than
the current value of the other stream, so it cannot be common with anything
still unseen.

Why it beats the hash set. It uses O(h1 + h2) memory instead of O(n), and
it stops at the first match. When the answer is near the top of both trees it
touches only a few nodes. The traversal is iterative, so a skewed tree with
10^5 nodes does not hit Python's recursion limit.

Duplicates: a valid BST in this problem holds distinct values, but the merge
still works if duplicates appear, because equal values return immediately.

Code

from __future__ import annotations

from dataclasses import dataclass
from typing import Iterator, Optional


@dataclass
class TreeNode:
    val: int
    left: Optional["TreeNode"] = None
    right: Optional["TreeNode"] = None


class DescendingBSTIterator:
    """Yields BST values from largest to smallest using O(height) memory."""

    def __init__(self, root: Optional[TreeNode]) -> None:
        self._stack: list[TreeNode] = []
        self._push_right_spine(root)

    def _push_right_spine(self, node: Optional[TreeNode]) -> None:
        while node is not None:
            self._stack.append(node)
            node = node.right

    def has_next(self) -> bool:
        return bool(self._stack)

    def peek(self) -> int:
        return self._stack[-1].val

    def advance(self) -> None:
        node = self._stack.pop()
        self._push_right_spine(node.left)


def largest_common_value(a: Optional[TreeNode], b: Optional[TreeNode]) -> int:
    """Return the largest value present in both BSTs, or -1 if none."""
    it_a, it_b = DescendingBSTIterator(a), DescendingBSTIterator(b)
    while it_a.has_next() and it_b.has_next():
        va, vb = it_a.peek(), it_b.peek()
        if va == vb:
            return va
        if va > vb:
            it_a.advance()   # va is larger than anything left in b
        else:
            it_b.advance()   # vb is larger than anything left in a
    return -1


def largest_common_value_hashset(a: Optional[TreeNode], b: Optional[TreeNode]) -> int:
    """Baseline: O(n + m) time, O(n) space; does not use BST ordering."""
    def values(root: Optional[TreeNode]) -> Iterator[int]:
        stack = [root] if root else []
        while stack:
            node = stack.pop()
            yield node.val
            stack.extend(c for c in (node.left, node.right) if c)

    seen = set(values(a))
    return max((v for v in values(b) if v in seen), default=-1)


def build_bst(values: list[int]) -> Optional[TreeNode]:
    """Insert values in order (iteratively) to build a test BST."""
    root: Optional[TreeNode] = None
    for v in values:
        if root is None:
            root = TreeNode(v)
            continue
        cur = root
        while True:
            if v < cur.val:
                if cur.left is None:
                    cur.left = TreeNode(v)
                    break
                cur = cur.left
            else:
                if cur.right is None:
                    cur.right = TreeNode(v)
                    break
                cur = cur.right
    return root


if __name__ == "__main__":
    t1 = build_bst([8, 3, 12, 1, 6, 10, 15])
    t2 = build_bst([7, 4, 11, 2, 6, 10, 14])
    assert largest_common_value(t1, t2) == 10
    assert largest_common_value(build_bst([5, 2, 9]), build_bst([4, 1, 7])) == -1
    assert largest_common_value(build_bst([42]), build_bst([42])) == 42
    assert largest_common_value(build_bst([-3, -7, -1]), build_bst([-5, -7])) == -7
    skew = TreeNode(0)  # right-skewed chain 0 -> 1 -> ... -> 99_999
    node = skew
    for v in range(1, 100_000):
        node.right = TreeNode(v)
        node = node.right
    assert largest_common_value(skew, build_bst([99_999])) == 99_999
    assert largest_common_value(build_bst([1, 2, 3]), build_bst([0])) == -1
    import random
    for _ in range(300):
        xs = random.sample(range(-50, 50), random.randint(1, 20))
        ys = random.sample(range(-50, 50), random.randint(1, 20))
        ta, tb = build_bst(xs), build_bst(ys)
        assert largest_common_value(ta, tb) == largest_common_value_hashset(ta, tb)
    print("all tests passed")

Complexity

Let n and m be the node counts and h1, h2 the heights.

Two-iterator merge: O(n + m) time in the worst case (no common value,
or the answer is the smallest value), since each node is pushed and popped
at most once. It often finishes much earlier. Space is O(h1 + h2): O(log n)
for balanced trees, O(n) for a fully skewed one.
Iterator operations: peek and has_next are O(1); advance is
amortized O(1) and worst case O(h).
Hash-set baseline: O(n + m) time, O(n) space.

Test cases

A = {1, 3, 6, 8, 10, 12, 15}, B = {2, 4, 6, 7, 10, 11, 14} → 10
(6 is also common, but 10 is larger).
A = {2, 5, 9}, B = {1, 4, 7} → -1 (no overlap, values interleave).
A = {42}, B = {42} → 42 (single nodes).
A = {-7, -3, -1}, B = {-7, -5} → -7 (negative values; answer is the
smallest value of A, so A is fully drained).
A = {1, 2, 3}, B = {0} → -1 (B's only value is below A's range).
A = 0..99,999 inserted in order (a skewed chain), B = {99,999} → 99999
(no recursion-depth failure; found on the first comparison).
Values at the bounds: A = {-10^9, 10^9}, B = {10^9} → 1000000000.
Note for the interviewer: -1 is ambiguous when -1 itself can be a
common value. Ask about it, and offer None or a (found, value) pair.

Follow-ups

All common values, or the k largest. Keep merging instead of
returning at the first match, and collect matches until you have k. The
ascending variant (normal in-order) lists all common values in sorted order.
Common to K trees. Keep one descending iterator per tree. While they
disagree, advance every iterator whose current value is greater than the
minimum of the current values. When all are equal, that is the answer.
O(total nodes) time, O(sum of heights) space.
Largest common value at most X. Seed each iterator by walking from the
root, pushing nodes with value ≤ X and moving right, and moving left
otherwise. Then merge as before. Only the seeding changes.
One tree is huge and the other tiny. For each value of the small tree,
in descending order, do an O(h) lookup in the big tree and return the
first hit. Cost is O(m · h1) instead of O(n + m), which wins when m is
much smaller than n / log n.
Many queries against changing trees. If the trees are queried often
and change rarely, keep a sorted multiset or count map of values present in
both and update it on each insert and delete, so a query is O(1) or
O(log n).

Interviewer expectations

Mid-level (L4)

States the hash-set solution and its cost without help.
Recognizes that in-order traversal of a BST is sorted and arrives at a
merge of two sorted sequences, possibly by first flattening both into lists.
Writes correct code with a clean -1 return and handles single-node trees.

Senior (L5)

Goes straight to the descending two-iterator merge with explicit stacks and
explains why the larger value can be discarded.
Gets O(h1 + h2) space and early exit, and avoids recursion on skewed input.
Raises the -1 ambiguity and duplicate values without being asked.

Staff (L6+)

Frames the iterator as a reusable abstraction and extends it to K trees,
upper bounds, and top-k with small changes.
Compares merge against per-value lookup by tree size and shape, and picks
one with numbers.
Discusses what changes when the trees are mutated concurrently or live on
different machines, for example streaming sorted values and merging them.