CODEWITHSUNDEEP
binary-search-tree
yaar zeigerman
yaar zeigerman

Reputation: 1117

Construction of BST from given Postorder Traversal

I have postorder array of a BST tree size n how do i show there is only one BST that can be constructed form it. I know I can rebuild the tree if I add nodes from right to left but how do I show there is only one right tree?

I have tried saying there are two possible trees and tried showing it is not possible but got stuck

Upvotes: 1

Views: 2757

Answers (1)

prelic
prelic

Reputation: 4518

It is possible only because it is a BST. Recall that for a Binary tree to be a valid Binary Search Tree:

-Left subtrees' values must be less than root's value
-Right subtrees' values must be greater than root's value
-Left and right subtrees must be valid binary search trees.

Because we know this must be the case, we can reconstruct the tree given a list of elements in post-order. The last element in the array (at pos n), is the root. Find the right-most element bigger than the root, and that's the root's first right-subtree. Find the element closest to the end of the array that is smaller than the root, and that's the left element. Recursively apply this to get the tree.

Example: 

[8,10,9,12,11]

      11 <----root

9 is the right-most number smaller than 11, so it's the left sub-tree

  11
 /
/

9

and 12 is the right-most element bigger than 11, so

    11
   /  \
  /    \
 9      12

Now, our root is 9, and the right-most number smaller than 9 is 8, so tree becomes 

       11
      /  \
     /    \
    9      12
   / \ 
  8

And the next number bigger than 9 is 10, so the final tree is

       11
      /  \
     /    \
    9      12
   / \ 
  8   10

Try and convince yourself that there are other possible valid binary search trees with these points, but not ones that produce identical output on a post-order traversal.

Upvotes: 5

Related Questions