I think I have managed to solve it. Comments welcome.
Firstly, let us consider the stack-less and recursion-less traversal of binary trees, where each node has a parent pointer.
This can be done by getting the leftmost node and successively getting the inorder successor. If a node has a right child, the inorder successor is the leftmost node in the right subtree. Otherwise, it is the first ancestor whose left child is an ancestor of given node.
For some nodes, getting the inorder successor may take O(height) time, but amortized over the whole tree, it takes O(n) time. Apologies for not proving this here; CLRS has a comprehensive proof. This fact will be used later on.
Secondly, observe the structure of the max-tree that will be created. It looks like a max heap. Hence, all root to node paths are strictly decreasing and similarly, all node to ancestor/root path is strictly increasing. This is an important point.
My algorithm scans the array from left to right, maintaining:
- A binary tree.
- A pointer to the last inserted node. This is like the hint in C++ STL map.
Done properly, it is exactly equivalent to the inorder traversal described above and thus, will take O(n) time.
Here is how insertions work:
Compare the array element being scanned to the just inserted binary tree node. If the array element is less than the current node, clearly it is a child. Otherwise, it is an ancestor.
If the new node is a child, I recursively construct the right subtree keeping in mind to not exceed the array boundary and also, not to exceed the value of the current pointer (no child can exceed the value of an ancestor).
If the new node is a parent, we simply have to go to the root of the current tree being constructed (local to the function) and attach it as a left child of a new node.
Here (Github gist) is the solution and testing code in C++. The testing code works by comparing the trees created by my algo and the obvious O(n log n) solution.
Edit: Forget the inorder traversal complexity proof. I am never traversing the height of the tree in my solution and scanning each element only once. Time complexity is O(n).
Comments/Suggestions are welcome.