OK, I solved ACM problem 1136 from USU's site(solution submitted and accepted). Here goes:

A postorder indeed uniquely defines a BST. I'm almost 100% sure - I have a totally deterministic algorithm (no choice whatsoever) that builds a BST from its postorder, but I can't prove the uniqueness formally. Never mind...

The algorithm goes as follows:

* vec: global stack of postorder numbers
* node is a BST node, contains a number,
and left & right pointers
* a window is a pair of numbers (L, R)

build_node (node, window)

    if vec is empty
        return END

    next = next number on stack

    if next is in the window
        pop the vec stack by 1

        new_node = new node(next)

        if next > node->num
            node-&g;tright = new_node
            new_window = (node->num, window->R)
            node->left = new_node
            new_window = (window->L, node->num)

        status = build_node(new_node, new_window)

        if status = END
            return END
        else if status = NOT_IN_LIMIT
            return build_node(node, window)

        return NOT_IN_LIMIT

    return OK

The idea is simple: in postorder, the last element is the root. The one before last is its son. Which son ? Depending on ordering. If it's larger than the root, right son, otherwise left son. And so we can descend recursively deep into the tree. But what happens once, say, the right line ends and the left descendant of the root appears ? We should backtrack back to the root and take left. So, "window" is used for this purpose. At each point we keep track of what values are legal. If a value out of the window is met, we backtrack.

I implemented it in C++, using deque for keeping postorder, and a simple node* struct for the tree. The most amazing thing is that this worked the first time I ran it, perfectly. Geez.


comments powered by Disqus