Preorder traversal of a BST
You have been given an array/list 'PREORDER' representing the preorder traversal of a BST with 'N' nodes. All the elements in the given array have distinct values.

Your task is to construct a binary search tree that matches the given preorder traversal.

A binary search tree (BST) is a binary tree data structure that has the following properties:

• The left subtree of a node contains only nodes with data less than the node’s data. • The right subtree of a node contains only nodes with data greater than the node’s data. • Both the left and right subtrees must also be binary search trees.

Note:

It is guaranteed that a BST can be always constructed from the given preorder traversal. Hence, the answer will always exist.

Example:

From PREORDER = [20, 10, 5, 15, 13, 35, 30, 42] , the following BST can be constructed:

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow. The first line of each test case contains a single integer 'N' denoting the number of nodes in BST. The second line of each test case contains 'N' single space-separated integers representing the preorder traversal of BST.

Output Format:

Print the inorder traversal of the constructed BST where all nodes are printed in a single-space separated manner. Output for every test case will be printed in a separate line. Note: You don't need to print anything. It has already been taken care of. Just implement the function.

Constraints :

1

Question

Preorder traversal of a BST

You have been given an array/list 'PREORDER' representing the preorder traversal of a BST with 'N' nodes. All the elements in the given array have distinct values.

Your task is to construct a binary search tree that matches the given preorder traversal.

A binary search tree (BST) is a binary tree data structure that has the following properties:

• The left subtree of a node contains only nodes with data less than the node’s data.
• The right subtree of a node contains only nodes with data greater than the node’s data.
• Both the left and right subtrees must also be binary search trees.

Note:

It is guaranteed that a BST can be always constructed from the given preorder traversal. Hence, the answer will always exist.

Example:

From PREORDER = [20, 10, 5, 15, 13, 35, 30, 42] , the following BST can be constructed:

example

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains a single integer 'N' denoting the number of nodes in BST.

The second line of each test case contains 'N' single space-separated integers representing the preorder traversal of BST.

Output Format:

Print the inorder traversal of the constructed BST where all nodes are printed in a single-space separated manner.

Output for every test case will be printed in a separate line.

Note:
You don't need to print anything. It has already been taken care of. Just implement the function.

Constraints :

1 <= T <= 100
1 <= N <= 5000
0 <= data <= 10^5

Where 'data' denotes data contained in the nodes of the binary search tree.

Time Limit: 1 sec

Accepted Answer

Brute Force Approach

We have a simple Brute Force solution for this problem. We will traverse the PREORDER array, find the left subtree and right subtree and then recursively construct the tree as follows-

The first element of the preorder traversal corresponds to the root of BST.
We will find the index ‘SPLIT’ of the first element in the given traversal which is greater than the root node i.e PREORDER[‘SPLIT’] > PREORDER['START'].
We will split the given array to the left subarray ['START' + 1 : ‘SPLIT’ - 1] and right subarray [‘SPLIT’: ‘END’] corresponding to the left subtree and right subtree, respectively.
We then recursively repeat the above steps for both subtrees to construct the complete tree.

Space Complexity: O(n)Explanation:

O(N), where N is the number of nodes in the BST.

O(H) recursion stack space is used by the algorithm. In the worst case, H will become N. Thus, space complexity is O(N).

Time Complexity: O(n^2)Explanation:

O(N^2), where N is the number of nodes in the BST.

For each node, we search for a split point to get the left and the right subtree. So, the overall time complexity is O(N^2).

C++ (g++ 5.4)

/*

    Time Complexity : O(N^2)

    Space Complexity : O(N)

    

    Where N denotes number of nodes in the array/list.

*/





BinaryTreeNode* helper(vector &preorder, int start, int end){

    if (start > end){

        return NULL;

    }

    

    

    // First element is the root of BST.

    BinaryTreeNode *root = new BinaryTreeNode(preorder[start]);

 

    int split;



    // Finding left and right subtree.

    for (split = start + 1; split <= end; split++) {

        if (preorder[split] > root -> data){

            break;

        }

    }

    

    // Recursively construct left and right subtrees.

    root -> left = helper(preorder, start + 1, split - 1);



    root -> right = helper(preorder, split, end);



    return root;

}



BinaryTreeNode* preorderToBST(vector &preorder){

    int n = preorder.size();

    int start = 0;

    int end = n - 1;



    BinaryTreeNode *root = helper(preorder, start, end);



    return root;

}

Python (3.5)

'''

    Time Complexity : O(N^2)

    Space Complexity : O(N)

    

    Where N denotes number of nodes in the array/list.

'''



class   TreeNode :

    def __init__(self, data) :

        self.data = data

        self.left = None

        self.right = None



    def __del__(self):

        if self.left:

            del self.left

        if self.right:

            del self.right



def helper(preorder, start, end):

    if start > end:

        return None



    # First element is the root of BST.

    root = TreeNode(preorder[start])



    split = start + 1



    # Finding left and right subtree.

    while split <= end:

        if preorder[split] > root.data:

            break



        split += 1

    

    # Recursively construct left and right subtrees.

    root.left = helper(preorder, start + 1, split - 1)

    root.right = helper(preorder, split, end)



    return root



def preorderToBST(preorder):



    n = len(preorder)

    start = 0

    end = n - 1



    root = helper(preorder, start, end)



    return root

Java (SE 1.8)

/*

    Time Complexity : O(N^2)

    Space Complexity : O(N)

    

    Where N denotes number of nodes in the array/list.

*/



import java.util.ArrayList;



public class Solution {

    static BinaryTreeNode prorderToBST(ArrayList preOrder) {

        int n = preOrder.size();

        int start = 0;

        int end = n - 1;



        BinaryTreeNode root = helper(preOrder, start, end);

        return root;

    }



    static BinaryTreeNode helper(ArrayList preOrder, int start, int end) {

        if (start > end) {

            return null;

        }



        // First element is the root of BST.

        BinaryTreeNode root = new BinaryTreeNode(preOrder.get(start));



        int split;



        // Finding left and right subtree.

        for (split = start + 1; split <= end; split++) {

            if (preOrder.get(split) > root.data) {

                break;

            }

        }



        // Recursively construct left and right subtrees.

        root.left = helper(preOrder, start + 1, split - 1);

        root.right = helper(preOrder, split, end);



        return root;

    }



}

Accepted Answer

Use BST property

The idea is based on the fact that the value of each node in a BST is greater than the value of all nodes in its left subtree and less than the value of all nodes in its right subtree.

So, instead of explicitly searching for indices that split the left and the right subtree (as in the previous approach), we will pass the information about the valid range of values for a node and its children in recursion itself.

We will maintain ‘MIN_VAL’ and ‘MAX_VAL’ (initialized to minimum and maximum possible value, respectively) to set a range for every node.
We will also maintain ‘PRE_ORDER_INDEX’to keep track of the index in the ‘PRE_ORDER_INDEX’ array.
We initialize ‘CURR_VAL’ to ‘PREORDER’[‘PRE_ORDER_INDEX’].
- If ‘CURR_VAL’ doesn’t fall in the range [‘MIN_VAL’: ‘MAX_VAL’ ], we return NULL.
- Else, we construct ‘NODE’ initialized to ‘CURR_VAL’ and increment ‘PRE_ORDER_INDEX’.
We will then set the range for the left subtree ([‘MIN_VAL’ : ‘CURR_VAL’ + ‘1’) and the right subtree (['CURR_VAL' +1 : ‘MAX_VAL’]) and recursively construct them.