more thoughts on previous problem

Ugh... it seems that postorder does UNIQUELY define a BST. It doesn't define just some unordered tree uniquely, but BST - it does.

Hmm...

I thought about one approach:

Given a postorder, the tree root is last. Taking the one-before-last number, we can immediately know which son of the root it is (bigger or smaller than the root ?). And so on, taking numbers from the end and building the tree

But this can't last forever, so I'm thinking of passing some "window" down through the recursion, and back-track if a new value doesn't fit in a window. In paper simulation it works, now I just have to think of a more definite algorithm.

Another idea (that my friend suggested) is that the last element is the root, and all the elements before it are clearly divided to two halves, those > root, and those root, his right and left descendants. And so recursively...