Codeforces Round #353 (Div. 2) - D. Tree Construction

Problem Statement:
Codeforces Round #353 (Div. 2) - D. Tree Construction

Summary:
Build a binary search tree by inserting a sequence of distinct elements one by one, and output the parent of each element.



Solution:
I also like this problem, especially since it is a good refresher to BST. This problem tests one particular property of BST: node visited by in-order traversal of BST appears in sorted order.

For another refresher, let's go through those 3 easily-forgotten and confusingly-named tree traversals: post-order, pre-order and in-order. The definitions are actually recursive on each subtree. Each subtree has a left subtree, a root, and a right subtree.
- Post-order (bottom-up): Traverse left subtree, traverse right subtree, visit root.
- Pre-order (top-down): Visit root, traverse left subtree, traverse right subtree.
- In-order (left to right): Traverse left subtree, visit root, traverse right subtree.

So back to the problem. All BST is sorted if read from left to right. Then we can think of this property as an invariant (or equivalence class if you may): No matter how a BST is build, in whatever order, for the same set of elements, the left-to-right relative ordering of the elements in all these BST are the same (i.e. following the sorted order).

Since insertion of an element a[i] must result in the BST still in sorted order, we know that a[i] must be placed in between two elements in BST that is just bigger and just smaller than a[i]. Or in another words, if the result of reading the BST in-order is b[1], b[2], ..., b[n] (remember they are sorted!), then a[i] must be placed in between b[j] and b[j+1] where b[j] < a[i] < b[j+1]. Hence knowing that a[i] can either be the child of b[j] or b[j+1] after insertion, we just need to check which of them has a vacancy for a[i]. It is guaranteed that only one of them will have a vacancy (either right side of b[j] or left side of b[j+1]). Why? Because if:
1) b[j] and b[j+1] both does not have vacancy, then we can find child of b[j] to the right, which must be b[j+1], and also a child to the left of b[j+1], which must be b[j], a contradiction since then we have a cycle and no longer a tree.
2) b[j] and b[j+1] both have vacancies, which means that both of them must be leaves. For two leaves of a tree, we can find the least common ancestor of the leaves, say v. We show that b[j] < v < b[j+1]. If v < b[j] < b[j+1], then there must be downward paths from v to b[j] and v to b[j+1] that does not intersect (since intersection of path means there is a lower level node that is ancestor to both b[j] and b[j+1]), but that means that v will have two right children! Similar argument for the case where b[j] < b[j+1] < v. Finally, since b[j] < v < b[j+1], we have contradiction since b[j] and b[j+1] should be consecutive when read from left to right.

Hence to solve the problem, for each step we just need to find the two nodes just larger and smaller than the element to be inserted, and update the vacancy information on either of the nodes. Then we insert the element to a balanced BST (like C++ set/map). So insertion is guaranteed to be O(n log n), without having to build the actual (possibly unbalanced) BST. It's like creating a 'cheaper' counterfeit tree, but different but still the same. Cool huh!