Graft Small Search Trees into One BST
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
The array `trees` contains roots of separate strict binary search trees. Each tree has at most three nodes and no grandchildren, and all root values are distinct. In one operation, replace a leaf of one current tree with another current tree whose root has that leaf value, then remove the second tree from the collection. Return the root of a valid strict BST formed using exactly `n-1` such operations, or `nullptr` if this is impossible. Use the given `TreeNode*` interface and the original trees.
```cpp
class Solution {
public:
TreeNode* canMerge(vector<TreeNode*>& trees);
};
```
### Examples
**Example 1:**
```text
Trees: root 4 with left leaf 2; root 2 with left leaf 1.
Output: root 4 with left child 2, whose left child is 1.
Explanation: Replace the leaf valued 2 by the second root; the result is a strict BST.
```
**Example 2:**
```text
Trees: root 4 with left leaf 2; root 2 with right leaf 5.
Output: nullptr
Explanation: The only graft puts 5 in the left subtree of 4, violating the BST rule.
```
### Constraints
- `1 <= trees.length <= 5 * 10^4`.
- Each input tree has 1 to 3 nodes, no grandchildren, and is a valid strict BST.
- Root values are distinct; all node values lie in `[1,5 * 10^4]`.
### Clarifying Questions
BST bounds apply to whole subtrees, not just parents. Return existing node pointers and perform real grafts; tree descriptions in examples are explanatory only.
```hint Inspect the structure
Which root value can survive without being grafted into another tree?
```
### Reasoning checkpoints
- Use only the permitted leaf-to-root replacements and incorporate every original tree when reporting success.
- Enforce strict BST inequalities throughout entire subtrees, including constraints imposed by ancestors.
- Preserve the original pointer-based input, returned root and grafting semantics.
### Optional extensions
Why is checking each immediate parent-child comparison insufficient?
Overview: Graft Small Search Trees into One BST. The vector trees contains roots of separate valid binary search trees, each with at most three nodes and no grandchildren. Root values are distinct. One operation replaces a leaf of one current tree by another current tree whose root has the same value, removing that second tree from the collection. Return the root of a strict BST obtainable after exactly n-1 operations, or nullptr if impossible. The interface uses actual TreeNode pointers.