# Construct Binary Search Tree from Preorder Traversal

Published: Jan 17, 2023

Medium Divide and Conquer Binary Search Tree

## Problem Description

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 there is always possible to find a binary search tree with the given requirements for the given test cases.

A binary search tree is a binary tree where for every node, any descendant of `Node.left` has a value strictly less than `Node.val`, and any descendant of `Node.right` has a value strictly greater than `Node.val`.

A preorder traversal of a binary tree displays the value of the node first, then traverses `Node.left`, then traverses `Node.right`.

Constraints:

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

https://leetcode.com/problems/construct-binary-search-tree-from-preorder-traversal/

## Examples

``````Example 1
Input: preorder = [8,5,1,7,10,12]
Output: [8,5,10,1,7,null,12]

8
/   \
5      10
/ \       \
1   7       12
``````
``````Example 2
Input: preorder = [1,3]
Output: [1,null,3]

1
\
3
``````

## How to Solve

A couple of approaches are there to solve this problem such as recursion, iterative, with inorder, etc. Among those, the divide and conquer (recursion) would be an easy one. The recursion approach might use indices or lower/upper bound values. The solution here uses the divide and conquer with indices.

The preorder array’s start index will be the current node’s value. The left subtree will be up to the index where the value is smaller than the current node. The right subtree will be the preorder array’s greater values than current node. After the recursion, BST will be created.

## Solution

``````/**
* Definition for a binary tree node.
* struct TreeNode {
*     int val;
*     TreeNode *left;
*     TreeNode *right;
*     TreeNode() : val(0), left(nullptr), right(nullptr) {}
*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class ConstructBinarySearchTreeFromPreorderTraversal {
private:
TreeNode* helper(vector<int> &preorder, int start, int end){
if (start > end) { return nullptr; }
TreeNode* root = new TreeNode(preorder[start]);
int idx = start + 1;
while (idx <= end && preorder[idx] < preorder[start]) {
idx++;
}
root -> left = helper(preorder, start + 1, idx - 1);
root -> right = helper(preorder, idx, end);
return root;
}
public:
TreeNode* bstFromPreorder(vector<int>& preorder) {
return helper(preorder, 0, preorder.size() - 1);
}
};
``````
``````/**
* Definition for a binary tree node.
* public 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;
*     }
* }
*/
class ConstructBinarySearchTreeFromPreorderTraversal {
private TreeNode helper(int[] preorder, int start, int end) {
if (start > end) { return null; }
TreeNode root = new TreeNode(preorder[start]);
int idx = start + 1;
while (idx <= end && preorder[idx] < preorder[start]) {
idx++;
}
root.left = helper(preorder, start + 1, idx - 1);
root.right = helper(preorder, idx, end);
return root;
}

public TreeNode bstFromPreorder(int[] preorder) {
return helper(preorder, 0, preorder.length - 1);
}
}
``````
``````/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
*     this.val = (val===undefined ? 0 : val)
*     this.left = (left===undefined ? null : left)
*     this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {number[]} preorder
* @return {TreeNode}
*/
var bstFromPreorder = function(preorder) {
const func = function helper(start, end) {
if (start > end) { return null; }
let root = new TreeNode(preorder[start]);
let idx = start + 1;
while (idx <= end && preorder[idx] < preorder[start]) {
idx += 1;
}
root.left = helper(start + 1, idx - 1);
root.right = helper(idx, end);
return root;
};
return func(0, preorder.length - 1);
};
``````
``````# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class ConstructBinarySearchTreeFromPreorderTraversal:
def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
def helper(start, end):
if start > end:
return None
root = TreeNode(preorder[start])
idx = start + 1
while idx <= end and preorder[idx] < preorder[start]:
idx += 1
root.left = helper(start + 1, idx - 1)
root.right = helper(idx, end)
return root
return helper(0, len(preorder) - 1)
``````
``````# Definition for a binary tree node.
# class TreeNode
#     attr_accessor :val, :left, :right
#     def initialize(val = 0, left = nil, right = nil)
#         @val = val
#         @left = left
#         @right = right
#     end
# end
# @param {Integer[]} preorder
# @return {TreeNode}
def bst_from_preorder(preorder)
helper = lambda do |start, last|
if start > last
return nil
end
root = TreeNode.new(preorder[start])
idx = start + 1
while idx <= last && preorder[idx] < preorder[start]
idx += 1
end
root.left = helper.call(start + 1, idx - 1)
root.right = helper.call(idx, last)
root
end
helper.call(0, preorder.size - 1)
end
``````

## Complexities

• Time: `O(n)`
• Space: `O(h)` – h: height of the tree