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.

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.

Description Solution Video 12:24

1008. Construct Binary Search Tree from Preorder Traversal

Q: 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.

Medium84.7% acceptance5 companies

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 <= 100
1 <= preorder[i] <= 1000
All the values of preorder are unique.

Asked at 5 companies

Amazon

Google Microsoft Meta Bloomberg

Topics

12:24

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1# Definition for a binary tree node.
2# class TreeNode:
3#     def __init__(self, val=0, left=None, right=None):
4#         self.val = val
5#         self.left = left
6#         self.right = right
7class Solution:
8    def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]:
9        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[8,5,1,7,10,12]

Input

[1,3]

Your code is saved on this device.Solution