[Solved]: Algorithm for constructing BST from post-order traversal

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 $yto 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. */