Algorithm for constructing BST from post-order traversal

Question

Given a post-order traversal of Binary Search tree with $k$ nodes, find an algorithm that constructs the BST.

My Algortihm

Let $n$ represent the next element to be inserted.

Let $P(y)$ represent the parent of node $y$.

1. We will read the traversal in reverse. The last element of the traversal is the root. Let $l = root$. $l$ will represent the element last inserted in the BST (except for the 3rd case below- where it will change to the parent).

Loop the following till there's no element left to be inserted

1. if $l<n$ then $n$ is the right child of $l$. For the next insertion, $l$ changes to it's right child and $n$ becomes the next element(in reverse order of traversal ).

2. else, if $l>n$ and $P(l)<n$ then $n$ is the left child of $l$. For the next insertion, $l$ changes to it's left child and $n$ becomes the next element(in reverse order of traversal).

3. else, if $l>n$ and $P(l)>n$ then $l$ becomes $P(l)$.($n$ hasn't been inserted - we loop with $l$ changed)

[Let $P(root)=- \infty$, so that the $2^{nd}$ case applies]

Complexity Analysis : Every element may contribute at max 3 comparisons, 1 each for - left child, right child and for finally leaving i.e. subtree has been constructed. Even if I missed a comparison or two, It should be constant no. of comparisons per element and no. of operations for node construction will also be constant per element. Hence, giving $O(k)$ time complexity.

Actual Question

If the algorithm is correct, I need the correctness proof for it. Yes, I thought I had the proof but then brain got fried and I am stuck and unable to reason succinctly.
If the algorithm is incorrect, then why? And what is time complexity of the most efficient algorithm for the same question?

Also, is the $O(k)$ complexity correctly calculated - irrespective of the correctness of the algorithm?

Answer 1

You are in the right track. But the algorithm is incomplete. You missed the case inserting element on the left sub tree and back.

Here is the modified algorithm: (Changes marked in bold)

Let $n$ represent the next element to be inserted.

Let $P(y)$ represent the parent of node $y$.

Let $g=G(y)$ represent the first node g on the path $y\to root$ such that $P(g)<g$.

1. We will read the traversal in reverse. The last element of the traversal is the root. Let $l = root$. $l$ will represent the element last inserted in the BST (except for the 3rd case below- where it will change to the parent). Let $g=root$ tracking $G(l)$, initialize empty stack $stkG$ storing previous $g$'s on current path.

2. Loop the following till there's no element left to be inserted

   1. if $l<n$ then $n$ is the right child of $l$. For the next insertion, $l$ changes to it's right child and $n$ becomes the next element(in reverse order of traversal ). Push $g$ on $stkG$, and let $g=l$.

   2. else, if $l>n$ and $\textbf{P(g)<n}$ then $n$ is the left child of $l$. For the next insertion, $l$ changes to it's left child and $n$ becomes the next element(in reverse order of traversal).

   3. else, if $l>n$ and $\textbf{P(g)>n}$ then $l$ becomes $\textbf{P(g)}$ and pop $g$ from $stkG$.($n$ hasn't been inserted - we loop with $l$ changed)

[Let $P(root)=- \infty$, so that the $2^{nd}$ case applies]

For correctness, you can prove the following loop invariant:

1. Root is the first inserted element. for each insertion except root, the parent element has been inserted before.
2. Each insertion $n$ correctly maintains the order between $n$ and $l$. ($n<l$ if $n$ is left child of $l$, $n>l$ otherwise)
3. After backtracking step 3, the next insertion always occurs on the left branch.

1 and 3 ensures the post-order traversal, while 2 ensures the BST.

For complexity:

1. insertion cost: each element is inserted exactly once.
2. traversal and comparison: the algorithm actually performs a post-order traversal in reverse order, with $O(1)$ comparison on each step.
3. $g$,$stkG$ maintain cost: each node, which is right child of parent, is pushed and popped from $stkG$ at most once.

Thus the time complexity is $O(k)$.

Alternative algorithm:[1]

Using a recursive procedure:

procedure BST_from_postorder(post, len, target)
/*
input: post[0..len-1] -- (partial) postorder traversal of BST
       len -- length of post to be processed.
       target -- a cutoff value to stop processing
Output: tree_ptr -- pointer to root of tree/sub tree constructed from post[len_rest..len-1]
        len_rest -- remaining length that has not been processed.
*/
 1. if len <= 0 or post[len-1] <= target, then return null.
 2. root <- new Node created from from post[len-1].
 3. (root->right, new_len) <- BST_from_postorder(post, len-1, post[len-1])
 4. (root->left, rest_len) <- BST_from_postorder(post, newlen, target)
 5. return (pointer to root, rest_len)

/* BST_from_postorder(post, length of post, -infinity)
 will return the BST construct from given postorder traversal. */