Largest value shared by two BSTs

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.

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")

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.

• 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.

1. 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.
2. 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.
3. 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.
4. 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.
5. 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).

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.