Insertion Orders for the Same Tree
HardTrees
Problem
nums is a permutation of 1..n. Inserting its values one by one, left to right, into an empty binary search tree (each new value becomes a leaf where its search falls off) produces a particular tree shape.
Count how many orderings of nums (including nums itself) produce exactly the same tree. Return the count modulo 10^9 + 7.
Example 1
- Input:
- nums = [2, 1, 3]
- Output:
- 2
Both [2, 1, 3] and [2, 3, 1] build root 2 with children 1 and 3.
Example 2
- Input:
- nums = [3, 4, 5, 1, 2]
- Output:
- 6
3 must come first; then [1, 2] and [4, 5] keep their internal order but can be interleaved in C(4, 2) = 6 ways.
Example 3
- Input:
- nums = [1, 2, 3]
- Output:
- 1
Constraints
- 1 ≤ nums.length ≤ 1000
- nums is a permutation of 1..n.
Hint
Show the first hint
The first value is always the root. Which constraints does an ordering need to satisfy after that?
Walkthrough
How to approach it
01Clarify before coding
- Does the original order count? Yes, so the minimum answer is 1.
- Is the input always a permutation of 1..n? Yes, values are distinct and dense.
- Why modulo? The count grows like a factorial; return it mod 10^9 + 7.
02Brute force
Generate every permutation, build its tree and compare with the target tree.
Cost: O(n! · n²): hopeless beyond n ≈ 10.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.