173. Construct a BST from a preorder traversal

Given an array of integers preorder, which represents the preorder traversal of a BST (i.e., binary search tree), construct the tree and return its root.

It is guaranteed that it is always possible to find a binary search tree with the given requirements for the given test cases.

Note : As there can be many possible correct answers, the compiler outputs true if the solution is correct, else false.

Example 1:

Input : preorder = [8, 5, 1, 7, 10, 12]

Output : [8, 5, 10, 1, 7, null, 12]

Explanation :

Below is the BST image

Example 2:

Input : preorder = [1, 3]

Output : [1, null, 3]

Explanation :

Below is the BST image

Now Your Turn!

Pick the correct output for the given input

Input : preorder = [5, 3, 2, 4, 6, 7]

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

  • 1 <= preorder.length <= 100
  • 1 <= preorder[i] <= 1000
  • All the values of preorder are unique.

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

Fun Facts

0
/**
* Definition for a binary tree node.
* struct TreeNode {
* int data;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int val) : data(val) , left(nullptr) , right(nullptr) {}
* };
**/
 
class Solution {
public:
TreeNode* bstFromPreorder(vector<int>& preorder) {
//your code goes here
}
};
Test Case

Input:

Nums
to save your code