Binary Search Tree from preorder traversal

By | February 29, 2016

Binary Search Tree from preorder traversal.

Problem statement to create a Binary Search Tree from a preorder traversal

Given only a preorder traversal of a binary search tree (BST), create a tree.

Example:

INPUT:array= {10, 5, 1, 8, 12, 15, 20}
OUTUT:
              10
           /     \
           5      15
         /  \    /  \
         1   8  12   20

Create a Binary Search Tree from a preorder traversal Solution:

Method 1: Brute Force (naive) approach using divide and conquer:-

  1. The first element is always the root.
  2. Then determine the index (i) of first element which is greater than the root.
  3. All elements till ‘i’ are a part of the left subtree.
  4. All elements from ‘i+1′ to ‘n-1′ are a part of the right subtree.
  5. Divide the tree at ‘i’ and recur for both left and right subtrees.

Solution code in C++ for constructing a binary search tree (BST) from a preorder traversal:

#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in the tree*/
struct node
{
   int data;
   node *left;
   node *right;
};

/*This function is used to create and
initialises new nodes*/
node *newNode(int key)
{
   node *temp=new node;
   temp->left=NULL;
   temp->right=NULL;
   temp->data=key;
   return temp;
}

/*This function is used to
print Inorder traversal*/
void Inorder(node *root)
{
   if(!root)
      return;
   Inorder(root->left);
   cout<<root->data<<" ";
   Inorder(root->right);
}

/*This function creates a tree from the 
preorder traversal*/
node* buildTree(int arr[], int *rootIndex,
int low, int high, int n)
{
   /*Base Case*/
   if(low > high || *rootIndex >= n)
      return NULL;
      
   /*Create first node as root*/
   node *root = newNode(arr[*rootIndex]);
   *rootIndex = *rootIndex+1;
   
   if (low == high)
      return root;
      
   /*Find first element greater than root*/
   int i;
   for(i=low; i<=high; i++)
   {
      if(arr[i] > root->data)
         break;
   }
   
   root->left = buildTree(arr, rootIndex,  *rootIndex, i-1, n);
   root->right = buildTree(arr, rootIndex, i, high, n);
   
   return root;
}

/*Driver function to test above functions*/
int main() {
   
    int arr[] = {10, 5, 1, 8, 12, 15, 20};
    int n = sizeof(arr)/sizeof(arr[0]);
    int rootIndex = 0;
    
    node *root = buildTree(arr, &rootIndex, 0, n-1, n);
   
    cout << "\nInorder traversal of the BST is: ";
    Inorder(root);
   return 0;
}

Output:

Inorder traversal of the BST is: 1 5 8 10 12 15 20

Time Complexity:

Average Case : O(nlogn)
Worst Case : O(n2)


Method 2: Using INT_MIN and INT_MAX:

Set a range for each node to lie between INT_MIN and INT_MAX. The root node always lies within the range. Similarly check for all other nodes while updating the min and max ranges w.r.t. the root for left and right subtree.

Algorithm for creating a Binary Search Tree from preorder traversal:

  1. Initialize INT_MIN and INT_MAX.
  2. The root node lies in this range.
  3. For the left subtree, the range is INT_MIN to root->data.
  4. For the right subtree, range is root->dta to INT_MAX.

Solution code in C++ to build Binary Search Tree from preorder traversal:

#include <bits/stdc++.h>
using namespace std;

/*Structure of each node in the tree*/
struct node
{
   int data;
   node *left;
   node *right;
};

/*This function is used to create and
initialises new nodes*/
node *newNode(int key)
{
   node *temp=new node;
   temp->left=NULL;
   temp->right=NULL;
   temp->data=key;
   return temp;
}

/*This function is used to
print Inorder traversal*/
void Inorder(node *root)
{
   if(!root)
      return;
   Inorder(root->left);
   cout<<root->data<<" ";
   Inorder(root->right);
}

/*This function creates a tree from the 
preorder traversal*/
node* buildTree(int arr[], int *rootIndex,int key,
int min, int max, int n)
{
   /*Base Case*/
   if( *rootIndex >= n)
      return NULL;
   
   /*Create a root*/
   node *root = NULL;
   
   /*If the current element lies in range,
   it belongs in the subtree*/
   if (key > min && key < max)
   {
      root = newNode(key);
      *rootIndex = *rootIndex + 1;
      
      if(*rootIndex < n)
      {
         root->left = buildTree(arr, rootIndex, 
         arr[*rootIndex], min, key, n);
         root->right = buildTree(arr, rootIndex, 
         arr[*rootIndex], key, max, n);	
      }
   }
   
   return root;
}

/*Driver function to test above functions*/
int main() {
   
    int arr[] = {10, 5, 1, 8, 12, 15, 20};
    int n = sizeof(arr)/sizeof(arr[0]);
    int rootIndex = 0;
    
    node *root = buildTree(arr, &rootIndex, arr[0], INT_MIN, INT_MAX, n);
   
    cout << "\nInorder traversal of the BST is: ";
    Inorder(root);
   return 0;
}

Output:

Inorder traversal of the BST is: 1 5 8 10 12 15 20

Time Complexity: O(n)


Method 3: Using Stacks:

We create an auxiliary stack which stores the data from the given preorder traversal.

Algorithm for creating a Binary Search Tree from preorder traversal:

  1. Create an empty stack.
  2. Initialize the first element as root and push it in the stack.
  3. Traverse from 1 to n-1 and compare each node with the topmost element of the stack.
  4. If it is smaller than the top element, then push it in the stack.
  5. Else pop the stack elements till topmost element of stack is greater than the node.

Solution code in C++ to build Binary Search Tree from preorder traversal:

#include<bits/stdc++.h>
using namespace std;

/*Structure of each node in the tree*/
struct node
{
   int data;
   node *left;
   node *right;
};

/*This function is used to create and
initialize new nodes*/
node *newNode(int key)
{
   node *temp = new node;
   temp->left = NULL;
   temp->right = NULL;
   temp->data = key;
   return temp;
}

/*This function is used to print 
Inorder traversal*/
void Inorder(node *root)
{
   if(!root)
      return;
   
   Inorder(root->left);
   cout<<root->data<<" ";
   Inorder(root->right);
}


/*This function creates a tree from the 
preorder traversal*/
node *buildTree(int arr[], int n)
{
   /*Create a stack*/
   stack<node*> s;
   
   /*Create first node as root*/
   node *root = newNode(arr[0]);
   
   /*Push the root in stack*/
   s.push(root);
   
   int i;
   node *temp;
   
   /*Traverse through n-1 nodes*/
   for(i=1 ; i<n; i++)
   {
      temp = NULL;
      
      while(!s.empty() && (arr[i]>s.top()->data))
      {
         temp = s.top();
         s.pop();
      }
         
      if(temp != NULL)
      {
         temp->right = newNode(arr[i]);
         s.push(temp->right);
      }
      
      else
      {
         s.top()->left = newNode(arr[i]);
         s.push(s.top()->left);
      }
      
   }
   return root;
}

/*Driver function to test above functions*/
int main(){
   
    int arr[] = {10, 5, 1, 8, 12, 15, 20};
    int n = sizeof(arr)/sizeof(arr[0]);
    int rootIndex = 0;
    
    node *root = buildTree(arr, n);
   
    cout << "\nInorder traversal of the BST is: ";
    Inorder(root);
   return 0;
}

 Output:

Inorder traversal of the BST is: 1 5 8 10 12 15 20

Time Complexity: O(n)