Binary Search Trees: Construct BST from preorder traversal

Problem Statement:

You are given an array representing a preorder traversal of a Binary Search Tree and construct the BST.

Solution

WKT the first element in a pre-order traversal is always the root.

So we take the first element as root, then we search for the element that is greater than the root.

Then the values before the greater element will be in the left sub tree, and the elements greater than the root will be in the right sub tree.

Example:

Consider the preorder array {8, 5, 1, 7, 10, 12}

We know that the first element in the root.

Then the element greater than the root is 10.

So we can divide the array into as below:

             8
           /    \
          /      \
  {5, 1, 7}       {10, 12}

Similarly we recursively follow the above steps and complete the tree.

Solution in C++

#include<iostream>
#include<vector>
#include<string>

using namespace std;


struct Node
{
    int data;
    struct Node *left, *right;
};
 


Node *get_new_node(int item)
{
    Node *temp =  new Node;
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}
 
Node* construct_BST(int preorder[], int start, int end)
{
    if (start > end) 
    {
        return NULL;
    }
 

   Node* node = get_new_node(preorder[start]);
 
    int i;
    for (i = start; i <= end; i++)
    {
        if (preorder[i] > node->data) {
            break;
        }
    }
 
    node->left = construct_BST(preorder, start + 1, i - 1);
 
    node->right = construct_BST(preorder, i, end);
 
    return node;
}

void print_inorder(Node* Node) 
{ 
    if (Node == NULL) 
        return; 
    print_inorder(Node->left); 
    cout<<" "<<Node->data; 
    print_inorder(Node->right); 
} 
  

int main()
{
    int preorder[] = { 15, 10, 8, 12, 20, 16, 25 };
    int n = sizeof(preorder)/sizeof(preorder[0]);
 
    struct Node* root = construct_BST(preorder, 0, n - 1);
 
    printf("Inorder traversal of BST is ");
 
    print_inorder(root); 

    return 0;
}

Output:

Inorder traversal of BST is 8 10 12 15 16 20 25