# Algorithm for constructing BST from post-order traversal

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?

• @TerenceHang Do we have an $O(n)$ algo for constructing Binary tree from post and inorder traversal? Because for comparing two elements we will need to refer the inorder and that won't be constant time comparison. May be we can hash the indexes of elements in inorder traversal in $O(n)$ time and then we can compare the indexes, but that would require restriction on key values. – PleaseHelp Sep 8 '15 at 3:24
• An $O(n)$ algo exists, based on node matching instead of relative order. Take the inorder and postorder traversal as 2 stacks $In$ and $Post$, adding a 3rd stack $stk$. 1. pop the root off $Post$, inserting to $stk$, and set insert position at right child of root. 2. whenever top of $In$ matches top of $stk$, pop this node $x$ from both $In$ and $stk$, changing insert position to left child of $x$. 3. pop a new node $n$ from $post$, insert $n$ at current insert position, and push $n$ on $stk$, setting insert position to right child of $n$. Repeat 2,3 until all 3 stack are empty. – Terence Hang Sep 8 '15 at 5:00
• Just find a $O(n)$ recursive algo [1] (It is for construction binary tree from preorder and inorder. Scanning in reverse order and changing the target we can make it for construction from postorder and inorder.) – Terence Hang Sep 8 '15 at 5:26
• What have you tried towards showing correctness, and where did you get stuck? Have you tried a more rigorous runtime analysis, too? See our reference questions for some pointers. – Raphael Sep 8 '15 at 7:17

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

• Hey, thanks for the answer. I understood your algorithm. For the correctness part 1 - this may also be added : "the right element is inserted before the left element". Also, I think my algorithm is correct too. You maintain a stack, so that you can directly jump to $P(g)$ in the $3^{rd}$ case. Instead, my algo does redundant comparison during backtracking from a left-subtree but eventually does reach $P(g)$ and inserts in the correct position. What do you think? – PleaseHelp Sep 7 '15 at 7:44
• There are cases where $n<l<P(l)$, which fall into your $3^{rd}$ case, but you have to decide to insert to left child or to backtrack. $g$ is used not only for quick backtracking, but also for comparison. – Terence Hang Sep 7 '15 at 7:50
• For correctness part, it is included in 3. ie. the traversal is always from right branch to left branch and never in reverse. – Terence Hang Sep 7 '15 at 7:53
• Ah! for $n<l<p(l)$, my algorithm always backtracks. So, if $n<l<p(l)$ & $P(g)<n$ then it will try to insert $n$ as left child of $g$ but that's obviously wrong. – PleaseHelp Sep 7 '15 at 8:42