Construct BST from the given Pre-Order Traversal

Problem Statement

Construct a BST from the preorder traversal of a Binary Search Tree (BST). Assume BST has a unique value at each node.

Example 

Input

preorder[] = {6, 3, 1, 4, 8, 7, 9}

Output

Naive Method

In this approach, we can observe that the first element of the preorder array will be the root of the binary search tree. We can observe that all the elements less than the root element will be part of the left subtree, and all the elements greater than the element's root will be present in the right subtree. We will recur for the left and right subtree and, in the end, return the root element.

Algorithm

1. First, we will create a base case to check if the value of pre has not exceeded the length of the preorder array (pre is the variable pointing to the 0th index of the preorder array) and if the value of l is greater than r (l and r are the variables to divide the preorder array to form the left subtree and right subtree).
2. Create a new node with the value preorder[pre] and increment the value of pre.
3. After creating a node, run a for loop from (l to r) to find the first element greater than the node’s value. Store the value if present.
4. Now divide the array into left and right subtrees and recur for both left and right subtrees. 

Dry Run

Step-1
In the first step, the pre will point to 6, and we will create a root node with the value 6, and the pre will be incremented. Here the left subtree will contain the elements {3,1,4} because all the elements are less than 6, and the right subtree will contain {8,7,9}, because all of them are greater than 6. So now we will recur for the left subtree.

Step-2

In the second step, the pre will point to 3; here, we will create a new node with the value 3, and after creating a new node, the pre will be incremented. Here the left subtree will contain the {1} because it is less than 3, and the right subtree will contain {4} because it is greater than 3. So now we will recur for the left subtree. Now again recurring for the left subtree.

Step-3

In this step, the value of pre will point at 1. A new node will be created with value 1, and the pre will be incremented. The left and right subtree of this element will be NULL.

Step-4

The value of pre will point at 4. A new node will be created with value 4, and the pre will be incremented. The left and right subtree of this element will be NULL.

Step-5

In this step, we will form the original right subtree and pre will point to 8, creating a node with the value 8. After this, we will repeat the same process in step 2.  

Step-6

In this step, the value of pre will point at 7. A new node will be created with value 7, and the pre will be incremented. The left and right subtree of this element will be NULL.

Step-7

In this step, the value of pre will point to 9. A new node will be created with the value 9, and the pre will be incremented. The left and right subtree of this element will be NULL.

Now, we can see that the whole tree has been formed.

Implementation in C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Tree
{
public:
    int value;
    Tree *left, *right;
    Tree(int value)
    {
        this->value = value;
        left = NULL;
        right = NULL;
    }
};

// Function to construct bst from preorder
Tree *constructTreeFromPreorder(vector<int> &preorder, int &pre, int l, int r)
{
    // base case
    if (pre >= preorder.size() || l > r)
        return NULL;

    // to handle cases of leaf nodes
    if (l == r)
        return new Tree(preorder[pre++]);

    Tree *root = new Tree(preorder[pre]);

    // increment the value of the pre
    pre++;

/*
Setting ind as r+1 because if there is no 
Element in the preorder, larger than the current
root then whole of the remaining array 
Belongs to the left subtree.

*/
    int ind = r+1;

    // to search for the first element in preorder greater than the root
    for (int i = l; i <= r; i++)
    {
        // if preorder value is greater than the root value then store the index
        if (preorder[i] > root->value)
        {
            ind = i;
            break;
        }
    }

    // divide the array into left and right subtrees
    root->left = constructTreeFromPreorder(preorder, pre, pre, ind - 1);
    root->right = constructTreeFromPreorder(preorder, pre, ind, r);

    return root;
}

void printInorder(Tree *root)
{
    if (root == NULL)
    {
        return;
    }
    printInorder(root->left);
    cout << root->value << " ";
    printInorder(root->right);
}

int main()
{

    vector<int> preorder = {6, 3, 1, 4, 8, 7, 9};

    int pre = 0;

    // Getting the Tree Constructed from it
    Tree *root = constructTreeFromPreorder(preorder, pre, 0, preorder.size() - 1);

    cout << "Inorder traversal of the above tree constructed is : " << endl;
    printInorder(root);
}

You can also try this code with Online C++ Compiler

Run Code

Output

Inorder traversal of the above tree constructed is : 
1 3 4 6 7 8 9 

Complexity Analysis

Time Complexity 

The time complexity would be O(N*N) because we will be traversing the whole preorder array, and for every node, we will use the for loop to find the greater element.

Space Complexity 

The space complexity would be O(N), which would be required to construct the tree.

Frequently Asked Questions

What is a BST (Binary Search Tree)?

BST is a binary tree in which every node of the tree should satisfy these two properties:

1. All the nodes in the left subtree should have lesser values than the value at the current node.
2. All the nodes in the right subtree should have values equal to or more than the value at the current node.

How is an inorder traversal of a BST always sorted?

In an inorder traversal, we first travel on the left subtree (values lower than the current node), then the root and the right subtree (values greater than or equal to values in the right subtree). So we are traversing the tree in a sorted manner. 

Left Subtree → Root → Right subtree.

What is the importance of inorder traversal in BST?

Inorder traversal is important for a BST because it visits all the nodes in the tree in ascending order of their values. This property is helpful for searching, sorting, and printing the nodes in a BST.

What is the time complexity of inorder traversal in a BST?

The time complexity of inorder traversal in a BST is O(n), where n is the number of nodes in the tree. This is because we visit each node once during the traversal.

Can a BST have duplicate values?

It depends on the implementation. In some implementations, a BST can have duplicate values, while in others, it cannot. If a BST allows duplicate values, it is called a Multiset or a Self-balancing Binary Search Tree.

Conclusion

This article taught us how to find the in-order traversal of a BST from its pre-order traversal. We also learned how to construct the BST from pre-order and inorder traversal.

Since Binary Search Tree is frequently asked in interviews, we recommend you practice more problems based on Binary Search Trees on Coding Ninjas Studio. 

I hope this blog has helped you enhance your knowledge regarding the above Data Structures and Algorithms problem, and if you want to learn more, check out our articles on Coding Ninjas Studio. Enroll in our courses, refer to the test series and problems available, and look at the interview bundle for placement preparations.

Recommended problems -

• Zig Zag Tree Traversal 
• Preorder Traversal

Nevertheless, you may consider our paid courses to give your career an edge over others!

Until then, All the best for your future endeavors, and Keep Coding.