Construct Binary Search Tree from Preorder Traversal

Return the root node of a binary search tree that matches the given preorder traversal.
(Recall that a binary search tree is a binary tree where for every node, any descendant of node.left has a value < node.val, and any descendant of node.right has a value > node.val.  Also, recall that a preorder traversal displays the value of the node first, then traverses node.left, then traverses node.right.)
It's guaranteed that for the given test cases there is always possible to find a binary search tree with the given requirements.

Example 1:

Input: preorder={8,5,1,7,10,12}
Output: [8,5,10,1,7,null,12]

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.stream.Collectors;

public class ConstructBinaryTreeFromPT {
    public static void main(String[] args) {
        int preorder[] = { 8, 5, 1, 7, 10, 12 };
        TreeNode root = bstFromPreorder(preorder);
        printTree(root);
    }

    static TreeNode bstFromPreorder(int[] preorder) {
        return bstPreorder(Arrays.stream(preorder).boxed().
                        collect(Collectors.toList()));
    }

    static TreeNode bstPreorder(List<Integer> preorder) {
        int n = preorder.size();
        if (n == 0)
            return null;
        List<Integer> left = new ArrayList<Integer>();
        List<Integer> right = new ArrayList<Integer>();
        int head = preorder.get(0);
        for (int i = 1; i < n; i++) {
            if (preorder.get(i) < head)
                left.add(preorder.get(i));
            else
                right.add(preorder.get(i));
        }
        TreeNode root = new TreeNode(head);
        root.left = bstPreorder(left);
        root.right = bstPreorder(right);
        return root;
    }

    static void printTree(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.add(root);
        List<String> vec = new ArrayList<String>();
        while (!q.isEmpty()) {
            root = q.poll();
            if (root == null)
                vec.add("null");
            else
                vec.add(String.valueOf(root.val));
            if (root != null) {
                q.add(root.left);
                q.add(root.right);
            }
        }
        int j = vec.size() - 1;
        while (j > 0 && vec.get(j) == "null")
            j--;
        for (int i = 0; i < j; i++)
            System.out.print(vec.get(i) + ",");
        System.out.print(vec.get(j));
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//struct for treenode
struct TreeNode{
    int data;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data=data;
        this->left=NULL;
        this->right=NULL;
    }
}; 

TreeNode* bstFromPreorder(vector<int>& preorder) 
{
     int n=preorder.size();
     if(n==0)
         return NULL;
     vector<int> Left,Right;
     int head=preorder[0];
     for(int i=1;i<n;i++)
     {
         if(preorder[i]<head)
             Left.push_back(preorder[i]);
         else
             Right.push_back(preorder[i]);
     }
     TreeNode *root=new TreeNode(head);
     root->left= bstFromPreorder(Left);
     root->right= bstFromPreorder(Right);
     return root;
}

//function to print the tree
void printTree(TreeNode *root)
{
    queue<TreeNode*>q;
    q.push(root);
    vector<string> vec;
    while(!q.empty())
     {
         root=q.front();
         q.pop();
         if(root==NULL)
            vec.push_back("null");
         else
            vec.push_back(to_string(root->data));
        if(root!=NULL)
          {
              q.push(root->left);
              q.push(root->right);
          }
     }
     int j=vec.size()-1;
     while(j>0&&vec[j]=="null")
        j--;
      vec.resize(j);
      for(int i=0;i<j;i++)
        cout<<vec[i]<<",";
      cout<<vec[j];
}
int main()
{
    vector<int> preorder={8,5,1,7,10,12};
    TreeNode *root=bstFromPreorder(preorder);

    printTree(root);
    return  0;

}