CODEWITHSUNDEEP
algorithm
premprakash
premprakash

Reputation: 1595

BST using preorder traversal

Is it possible to construct a Binary Search Tree Given only its preorder traversal ?

I know a binary tree can be constructed only if both inorder and preorder traversal are given . But my question is specific to Binary Search Tree .

eg: Given : 5,3,1,4,7,8

  Construct : 

       5
    3    7 
  1   4    8

Upvotes: 5

Views: 4948

Answers (4)

kaushalpranav
kaushalpranav

Reputation: 2184

Here you are using the inorder property of numbers while constructing the tree.

  1. A tree is fixed for a particular inorder and preorder.
  2. If only inorder is given, infinite possibilities are there for a tree.
  3. Similarly, if only preorder is given, infinite possibilities are there for a tree.

Ex : 

     a                             a
   /   \                            \
  b     e     and                    b
 / \   / \                            \
d  c  f   g                            d 
                                        \
                                         c
                                          \ 
                                           e
                                            \
                                             f
                                              \
                                               g

Both of the above trees have the same preorder i.e., a, b, d, c, e, f, g

This is because we are not considering any ordering between the given elements as the numbers in the case you gave.

If you require the ordering as you are using the BST, this link provides the solution.

http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/

Upvotes: 1

premprakash
premprakash

Reputation: 1595

A better explanation is provided here ..

http://www.geeksforgeeks.org/archives/25203

Upvotes: 1

premprakash
premprakash

Reputation: 1595

Based on the above algorithm .. my implementation in c++

node* buildtree(int[] preOrder,int start,int end) {

  if(start>end) return NULL;

  node *t = malloc(sizeof(node));

  // finds the index of the first element greater than preOrder[start]
  int index = find_index(preOrder, preOrder[start], start+1, end); 

  t->left = buildtree(preOrder,start+1,index-1);
  t->right = buildtree(preOrder,index,end);

  return t;

}

int find_index(int[] preOrder, int search_element, int start, int end) {

  for(int i=start;i<=end;i++) {
      if(preOrder[i]>search_element) return i;
  }
   return end+1;
 }

Upvotes: 0

krjampani
krjampani

Reputation: 2982

Yes, you can construct a binary search tree from a pre-order traversal. Given a pre-order traversal a_1, ..., a_n, divide it into three segments a_1, (a_2,...,a_k) and (a_{k+1},..,a_n), with the property that a_{k+1} is the first element in the pre-order that is greater than a_1.

Recursively compute the BST T1 of (a_2,...,a_k) and BST T2 of (a_{k+1},..,a_n) and add them as the left and the right subtrees of a new BST rooted at a_1.

Upvotes: 12

Related Questions