How would you implement a treap with split and merge?

1. Problem and context

Maintain a dynamic ordered set that supports search, insertion, deletion, and occasional splitting by key followed by a merge. Implement a treap: each node satisfies a binary-search-tree invariant on key and a max-heap invariant on random priority. Assume unique keys first, then explain duplicate handling.

2. What the interviewer is testing

• Explain what the BST invariant and heap invariant each provide.
• Compose insert and erase from split and merge instead of memorizing only rotations.
• State that O(log n) is expected, and that random quality and priority collisions affect shape.
• Maintain subtree size or aggregates, with correct update order and empty-child handling.

3. Questions to clarify first

• Are keys unique? If duplicates are allowed, put equal keys consistently on one side or use (key, id) as a composite key.
• Are priorities supplied by callers or generated internally? Internal generation needs a random source, collision policy, and reproducible test seed.
• Does split put the boundary key on the left, or require a strict less-than split? This changes insertion and range-query code.
• Do we need k-th order statistics, range sums, or an implicit sequence? Each mutation must then update subtree metadata.

4. Thirty-second answer framework

“I keep BST order by key and a max-heap order by a random priority. The core operations are split(T, key), returning keys at most the boundary and keys above it, and merge(L, R), which assumes every key in L is at most every key in R and chooses the higher-priority root. Insert splits around the new key and merges it back; erase merges the target’s children. Every recursive return updates size. Height and operations are expected O(log n), not worst-case, so production code needs reproducible tests, depth monitoring, or a tree with a deterministic bound.”

5. Step-by-step reasoning

First fix the invariants. For every node, left keys are no greater than its key, right keys are greater, and its priority is at least both child priorities. This article uses “equal keys go left”; a composite (key, uniqueId) is another unambiguous policy.

Second implement split. If the root key is at most the boundary, the root and left subtree belong to the left result, so recurse into the right child. Otherwise recurse into the left child for the right result. Reconnect the returned child and update size. Only one root-to-leaf path is visited.

Third implement merge. Handle an empty tree first. If the left root has higher priority, keep it as root and merge its right child with the right tree; otherwise keep the right root and merge the left tree with its left child. The precondition that every left key is no greater than every right key preserves BST order.

Fourth compose operations. For insert, split(root, key) and then merge(merge(left, node), right). For erase, replace the target with merge(node.left, node.right). Search descends by key and needs no split. If size is stored, run size = 1 + size(left) + size(right) after every split, merge, insert, and erase.

Fifth discuss complexity and failure. Random priorities make the shape comparable to a randomly built BST, giving expected O(log n) operations; CP-Algorithms documents logarithmic expected split, merge, insertion, and deletion. Nearly monotonic priorities can still create an O(n) tree, so use fixed seeds in tests, monitor height, or choose AVL or red-black trees when a worst-case bound is mandatory.

6. High-quality sample answer

“I would first agree on duplicate-key semantics, then implement two primitives. split returns left and right trees around a boundary, recursively splits one child, and reconnects the root. merge assumes all left keys are no greater than right keys and chooses the higher-priority root. Insert splits and puts the new node between the results; erase merges the target’s children. Updating subtree size also enables k-th selection. Random priorities give expected O(log n) height, not a worst-case guarantee, so I would test with fixed seeds across empty trees, duplicates, and long traces, monitor depth, and choose a red-black tree when deterministic bounds matter.”

7. Common mistakes

• Mistake → Maintain only BST order → sorted inserts still form a linked list → maintain the priority heap invariant too.
• Mistake → Merge without checking key ranges → searches take the wrong path → document that left keys are no greater than right keys.
• Mistake → Forget to update subtree size after split → k-th and range statistics drift → pull metadata immediately after reconnecting children.
• Mistake → Treat expected O(log n) as a worst-case guarantee → adversarial priorities can create a deep tree → monitor depth or use AVL/red-black trees.
• Mistake → Inconsistent duplicate policy across search, erase, and split → equal keys land in the wrong subtree → use a composite key or one boundary rule.

8. Follow-up questions

How do you support the k-th smallest element?

Store subtree size at every node. Compare k with the left size while descending; update size on every split, merge, insertion, and erase or the query becomes incorrect.

How can a treap represent an implicit sequence?

Do not store explicit keys. Define a node’s position from its left-subtree size plus ancestor contributions. Split by position and merge back to support insertion, deletion, and range aggregates; lazy flags can handle range reversal or addition.

When would you avoid a treap?

Choose AVL, a red-black tree, or a database index when strict worst-case O(log n), controlled randomness, or a mature concurrent implementation is required. Treaps trade that guarantee for short code and flexible split/merge composition.