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
.