Construct Binary Search Tree from Preorder Traversal solution and explanation
Google
9 more videos on this problem
Construct binary search tree from preorder traversal | Leetcode #1008Techdose · 12:24 · 60K views
Construct Binary Search Tree from Preorder Traversal | LeetCode 1008 | JavaProgramming Tutorials · 15:45 · 2K views
Construct BST from Preorder Traversal - LeetCode 1008daose · 9:52 · 1K views
Construct Binary Search Tree from Preorder Traversal | leetcode 1008 | EnglishCodebix · 14:21 · 907 views
Leetcode 1008 Construct Binary Search Tree from Preorder TraversalRen Zhang · 10:39 · 812 views
LeetCode 1008. Construct Binary Search Tree from Preorder TraversalHappy Coding · 13:49 · 708 views
1008. Construct Binary Search Tree from Preorder Traversal (Leetcode Medium)Programming Live with Larry · 22:27 · 471 views
Daily Leetcode #561: Oct 13, 2021 - 1008. Construct Binary Search Tree from Preorder TraversalProgramming Live with Larry · 10:53 · 287 views
LeetCode 1008 | Construct Binary Search Tree from Preorder Traversal | preOrder Traversal | JavaSleepy Cracker · 5:31 · 61 views
LEETCODE 1008 MEDIUM - Construct Binary Search Tree from Preorder TraversalIan Rosen · 8:50 · 57 views
The problem
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.
Example 1:
Input: preorder = [8,5,1,7,10,12] Output: [8,5,10,1,7,null,12]
Example 2:
Input: preorder = [1,3] Output: [1,null,3]
Constraints:
1 <= preorder.length <= 1001 <= preorder[i] <= 1000- All the values of
preorderare unique.
Approach overview
Problem Overview: Given an array representing the preorder traversal of a Binary Search Tree, reconstruct the original BST and return its root. The preorder order guarantees that every node appears before its left and right subtree, while BST rules ensure left < root < right.
Approach 1: Recursive Insertion (Time: O(n^2), Space: O(h))
This approach builds the tree the same way values would be inserted into a normal BST. Iterate through the preorder array and insert each value into the tree using a recursive BST insert routine. For every insertion, traverse left or right depending on the value comparison until you find the correct position. The logic is simple and mirrors standard BST operations, which makes it easy to implement during interviews. The drawback is performance: if the preorder array is sorted, the BST becomes skewed and each insertion scans most of the tree, resulting in O(n^2) time.
Approach 2: Stack-based Iterative Construction (Time: O(n), Space: O(n))
This optimized method uses a stack to track the path of nodes whose right child hasn't been assigned yet. Start by creating the root from the first preorder value and push it onto the stack. For each next value, check the top of the stack. If the value is smaller, it becomes the left child of the top node. If the value is larger, pop nodes until you find the correct parent where the value should be attached as the right child. The stack maintains a decreasing sequence of ancestors, similar to a monotonic stack. Each element is pushed and popped at most once, giving O(n) time complexity.
The key insight comes from preorder traversal properties: nodes appear in root-left-right order, so once you encounter a value greater than a node, you've finished that node's left subtree and are moving to the right subtree. The stack efficiently tracks this transition.
Recommended for interviews: Interviewers typically expect the O(n) stack solution because it demonstrates understanding of preorder traversal constraints and Binary Search Tree structure. The recursive insertion approach still helps show baseline reasoning and correctness before optimizing.
Approach 1: Approach 1: Recursive Insertion
In this approach, you will construct the binary search tree (BST) by recursively inserting nodes. The property of the BST is used where, for each node, nodes in the left subtree are less, and nodes in the right subtree are greater.
Start with the first element from the preorder sequence, which will be the root. Recursively insert subsequent elements using the BST insertion logic, and this will ensure that the tree constructed respects both the structure of a BST and adheres to the given preorder traversal.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def insertIntoBST(self, root, val):
if not root:
return TreeNode(val)
if val < root.val:
root.left = self.insertIntoBST(root.left, val)
else:
root.right = self.insertIntoBST(root.right, val)
return root
def bstFromPreorder(self, preorder):
if not preorder:
return None
root = TreeNode(preorder[0])
for val in preorder[1:]:
self.insertIntoBST(root, val)
return rootclass TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val)
root.left = insertIntoBST(root.left, val);
else
root.right = insertIntoBST(root.right, val);
return root;
}
public TreeNode bstFromPreorder(int[] preorder) {
if (preorder.length == 0) return null;
TreeNode root = new TreeNode(preorder[0]);
for (int i = 1; i < preorder.length; i++) {
insertIntoBST(root, preorder[i]);
}
return root;
}
}#include <iostream>
#include <vector>
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* insertIntoBST(TreeNode* root, int val) {
if (root == NULL) return new TreeNode(val);
if (val < root->val)
root->left = insertIntoBST(root->left, val);
else
root->right = insertIntoBST(root->right, val);
return root;
}
TreeNode* bstFromPreorder(std::vector<int>& preorder) {
if (preorder.empty()) return NULL;
TreeNode* root = new TreeNode(preorder[0]);
for (size_t i = 1; i < preorder.size(); ++i) {
insertIntoBST(root, preorder[i]);
}
return root;
}function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
function insertIntoBST(root, val) {
if (root === null) return new TreeNode(val);
if (val < root.val) {
root.left = insertIntoBST(root.left, val);
} else {
root.right = insertIntoBST(root.right, val);
}
return root;
}
function bstFromPreorder(preorder) {
if (!preorder.length) return null;
let root = new TreeNode(preorder[0]);
for (let i = 1; i < preorder.length; i++) {
insertIntoBST(root, preorder[i]);
}
return root;
}#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* newNode(int val) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = node->right = NULL;
return node;
}
struct TreeNode* insertIntoBST(struct TreeNode* root, int val) {
if (root == NULL) return newNode(val);
if (val < root->val)
root->left = insertIntoBST(root->left, val);
else
root->right = insertIntoBST(root->right, val);
return root;
}
struct TreeNode* bstFromPreorder(int* preorder, int preorderSize) {
if (preorderSize == 0) return NULL;
struct TreeNode* root = newNode(preorder[0]);
for (int i = 1; i < preorderSize; i++) {
insertIntoBST(root, preorder[i]);
}
return root;
}public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode InsertIntoBST(TreeNode root, int val) {
if (root == null) return new TreeNode(val);
if (val < root.val)
root.left = InsertIntoBST(root.left, val);
else
root.right = InsertIntoBST(root.right, val);
return root;
}
public TreeNode BstFromPreorder(int[] preorder) {
if (preorder.Length == 0) return null;
TreeNode root = new TreeNode(preorder[0]);
for (int i = 1; i < preorder.Length; i++) {
InsertIntoBST(root, preorder[i]);
}
return root;
}
}The Python solution provides a simple and idiomatic way of constructing the BST using recursive function calls. It takes a list of integers and initializes the BST by inserting the tail elements using recursive logic.
Time Complexity: O(n^2) in the worst case of an unbalanced tree as every insertion can take O(n).
Space Complexity: O(n) due to recursion stack overhead and node allocations.
Approach 2: Approach 2: Stack-based Iterative Construction
This approach uses a stack to iteratively construct the BST from the preorder traversal, which helps in achieving better average performance. Begin with the root node from the first preorder element, and iterate over the rest of the array with a technique to adjust parents as potential ancestors using a stack. Primary benefit is an average O(n log n) time complexity due to more constant-time parent-backtracking via stack use.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def bstFromPreorder(self, preorder):
if not preorder:
return None
root = TreeNode(preorder[0])
stack = [root]
for val in preorder[1:]:
node = TreeNode(val)
if val < stack[-1].val:
stack[-1].left = node
else:
parent = None
while stack and stack[-1].val < val:
parent = stack.pop()
parent.right = node
stack.append(node)
return rootimport java.util.Stack;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode bstFromPreorder(int[] preorder) {
if (preorder.length == 0) return null;
TreeNode root = new TreeNode(preorder[0]);
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
for (int i = 1; i < preorder.length; ++i) {
TreeNode node = new TreeNode(preorder[i]);
if (node.val < stack.peek().val) {
stack.peek().left = node;
} else {
TreeNode parent = null;
while (!stack.isEmpty() && stack.peek().val < node.val) {
parent = stack.pop();
}
parent.right = node;
}
stack.push(node);
}
return root;
}
}#include <iostream>
#include <vector>
#include <stack>
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* bstFromPreorder(std::vector<int>& preorder) {
if (preorder.empty()) return NULL;
TreeNode* root = new TreeNode(preorder[0]);
std::stack<TreeNode*> stk;
stk.push(root);
for (size_t i = 1; i < preorder.size(); ++i) {
TreeNode* node = new TreeNode(preorder[i]);
if (node->val < stk.top()->val) {
stk.top()->left = node;
} else {
TreeNode* parent;
while (!stk.empty() && stk.top()->val < node->val) {
parent = stk.top();
stk.pop();
}
parent->right = node;
}
stk.push(node);
}
return root;
}function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
function bstFromPreorder(preorder) {
if (!preorder.length) return null;
let root = new TreeNode(preorder[0]);
let stack = [root];
for (let i = 1; i < preorder.length; i++) {
let node = new TreeNode(preorder[i]);
if (node.val < stack[stack.length - 1].val) {
stack[stack.length - 1].left = node;
} else {
let parent;
while (stack.length > 0 && stack[stack.length - 1].val < node.val) {
parent = stack.pop();
}
parent.right = node;
}
stack.push(node);
}
return root;
}#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* newNode(int val) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = val;
node->left = node->right = NULL;
return node;
}
struct TreeNode* bstFromPreorder(int* preorder, int preorderSize) {
if (preorderSize == 0) return NULL;
struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * preorderSize);
int stackTop = -1;
struct TreeNode* root = newNode(preorder[0]);
stack[++stackTop] = root;
for (int i = 1; i < preorderSize; i++) {
struct TreeNode* node = newNode(preorder[i]);
if (node->val < stack[stackTop]->val) {
stack[stackTop]->left = node;
} else {
struct TreeNode* parent;
while (stackTop >= 0 && stack[stackTop]->val < node->val) {
parent = stack[stackTop--];
}
parent->right = node;
}
stack[++stackTop] = node;
}
free(stack);
return root;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public TreeNode BstFromPreorder(int[] preorder) {
if (preorder.Length == 0) return null;
TreeNode root = new TreeNode(preorder[0]);
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.Push(root);
for (int i = 1; i < preorder.Length; ++i) {
TreeNode node = new TreeNode(preorder[i]);
if (node.val < stack.Peek().val) {
stack.Peek().left = node;
} else {
TreeNode parent = null;
while (stack.Count > 0 && stack.Peek().val < node.val) {
parent = stack.Pop();
}
parent.right = node;
}
stack.Push(node);
}
return root;
}
}This Python solution constructs the BST iteratively by keeping a stack that assists in navigating ancestor nodes when child placement occurs. The slide down and assignment logic are handled within the loop.
Time Complexity: O(n), minimal extra operations per element processed.
Space Complexity: O(n) owing to the auxiliary stack representation.
Approach 3: DFS + Binary Search
We design a function dfs(i, j) to construct a binary search tree from the nodes preorder[i] to preorder[j]. The answer is dfs(0, n - 1).
In dfs(i, j), we first construct the root node, which is preorder[i]. Then, we use binary search to find the first node greater than preorder[i] and get its index mid. We set dfs(i + 1, mid - 1) as the left subtree of the root node and dfs(mid, j) as the right subtree of the root node.
Finally, we return the root node.
The time complexity is O(n times log n), and the space complexity is O(n). Here, n is the length of the array preorder.
/**
* Definition for a binary tree node.
* class TreeNode {
* val: number
* left: TreeNode | null
* right: TreeNode | null
* constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
* }
*/
function bstFromPreorder(preorder: number[]): TreeNode | null {
const dfs = (i: number, j: number): TreeNode | null => {
if (i > j) {
return null;
}
const root = new TreeNode(preorder[i]);
let [l, r] = [i + 1, j + 1];
while (l < r) {
const mid = (l + r) >> 1;
if (preorder[mid] > preorder[i]) {
r = mid;
} else {
l = mid + 1;
}
}
root.left = dfs(i + 1, l - 1);
root.right = dfs(l, j);
return root;
};
return dfs(0, preorder.length - 1);
}/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func bstFromPreorder(preorder []int) *TreeNode {
var dfs func(i, j int) *TreeNode
dfs = func(i, j int) *TreeNode {
if i > j {
return nil
}
root := &TreeNode{Val: preorder[i]}
l, r := i+1, j+1
for l < r {
mid := (l + r) >> 1
if preorder[mid] > preorder[i] {
r = mid
} else {
l = mid + 1
}
}
root.Left = dfs(i+1, l-1)
root.Right = dfs(l, j)
return root
}
return dfs(0, len(preorder)-1)
}// Definition for a binary tree node.
// #[derive(Debug, PartialEq, Eq)]
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
use std::cell::RefCell;
use std::rc::Rc;
impl Solution {
pub fn bst_from_preorder(preorder: Vec<i32>) -> Option<Rc<RefCell<TreeNode>>> {
fn dfs(preorder: &Vec<i32>, i: usize, j: usize) -> Option<Rc<RefCell<TreeNode>>> {
if i > j {
return None;
}
let root = Rc::new(RefCell::new(TreeNode::new(preorder[i])));
let mut l = i + 1;
let mut r = j + 1;
while l < r {
let mid = (l + r) >> 1;
if preorder[mid] > preorder[i] {
r = mid;
} else {
l = mid + 1;
}
}
let mut root_ref = root.borrow_mut();
root_ref.left = dfs(preorder, i + 1, l - 1);
root_ref.right = dfs(preorder, l, j);
Some(root.clone())
}
dfs(&preorder, 0, preorder.len() - 1)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Recursive Insertion | Time Complexity: O(n^2) in the worst case of an unbalanced tree as every insertion can take O(n). |
| Approach 2: Stack-based Iterative Construction | Time Complexity: O(n), minimal extra operations per element processed. |
| DFS + Binary Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive Insertion | O(n^2) worst case | O(h) | Simple implementation when demonstrating BST insertion logic |
| Stack-based Iterative Construction | O(n) | O(n) | Optimal solution for large inputs and interview expectations |
Frequently asked questions
Is Construct Binary Search Tree from Preorder Traversal easy or hard?
This problem is generally classified as Medium difficulty. The recursive insertion approach is straightforward, but identifying the O(n) stack optimization requires understanding preorder traversal properties and BST constraints.
Construct Binary Search Tree from Preorder Traversal Python/Java solution
Most solutions implement either recursive BST insertion or the stack-based iterative approach. Python and Java versions typically create nodes while scanning the preorder list and maintain a stack to assign left or right children. The stack method runs in O(n) time and is the preferred implementation in interviews.
How to solve Construct Binary Search Tree from Preorder Traversal in O(n)?
Use a stack to track nodes whose right subtree has not yet been constructed. Start with the first value as the root and push it to the stack. For each next value, attach it as the left child if it is smaller than the stack top; otherwise pop nodes until you find the correct parent and attach it as the right child. Each node is handled once, giving O(n) time.
What is the best approach for Construct Binary Search Tree from Preorder Traversal?
The optimal approach uses a stack to construct the BST in O(n) time. By processing preorder values sequentially and maintaining a stack of ancestors, you can determine whether the next value is a left child or the right child of a previously visited node. Each element is pushed and popped at most once, making it linear time.
Is Construct Binary Search Tree from Preorder Traversal asked at Google/Amazon/Meta?
Binary Search Tree reconstruction problems appear frequently in interviews at companies like Amazon, Google, and Meta. Variants include building a BST from preorder, validating BST properties, or reconstructing trees from traversal orders. The stack-based linear solution demonstrates strong understanding of tree traversal patterns.
What data structure is used in Construct Binary Search Tree from Preorder Traversal?
The problem primarily uses a Binary Search Tree structure combined with a stack for the optimal algorithm. The stack tracks the chain of ancestor nodes while processing preorder values. This allows efficient detection of transitions between left and right subtrees.
What is the time complexity of Construct Binary Search Tree from Preorder Traversal?
The optimal stack-based solution runs in O(n) time because each preorder value is processed once. A simpler recursive insertion approach may degrade to O(n^2) in the worst case when the tree becomes skewed. Space complexity ranges from O(h) for recursion depth to O(n) when using an explicit stack.