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

Problem Detail: 

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?

Asked By : atulgangwar

Answered By : Terence Hang

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/46893