we have a permutation p of size `N`

.

we iterate on this permutation and insert elements into a Binary Search Tree.

Prove that each sub-tree will consists of all elements from some `l`

to `r`

.

In other words, prove that elements of each sub-tree form continuous subarray of identity permutation (if written is sorted order).

`identity permutation`

-> `1, 2, 3, 4 ... N`

.

Auto comment: topic has been updated by Misa-Misa (previous revision, new revision, compare).Proof by induction.

Base case: $$$n \le 1$$$. Trivial.

Induction: Let us assume that we inserted $$$k$$$ first from the permutation of length $$$n$$$. Then, all elements smaller than $$$k$$$ will be on the left subtree, and the rest are on the right subtree. Then the left subtree is a permutation of $$$[1,k-1]$$$, and the right subtree is a permutation of $$$[k+1,n]$$$. A permutation of $$$[1,k-1]$$$ is a permutation of length $$$k-1$$$, and a permutation of $$$[k+1,n]$$$ is similarly a permutation of length $$$n-k$$$. Thus the induction holds.

Got it. Thanks.