# 1008. Construct Binary Search Tree from Preorder Traversal

• Time: $O(n)$
• Space: $O(h)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution { public: TreeNode* bstFromPreorder(vector& preorder) { TreeNode* root = new TreeNode(preorder[0]); stack stack{{root}}; for (int i = 1; i < preorder.size(); ++i) { TreeNode* parent = stack.top(); TreeNode* child = new TreeNode(preorder[i]); // Adjust parent while (!stack.empty() && stack.top()->val < child->val) parent = stack.top(), stack.pop(); // Create parent-child link according to BST property if (parent->val > child->val) parent->left = child; else parent->right = child; stack.push(child); } return root; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { public TreeNode bstFromPreorder(int[] preorder) { TreeNode root = new TreeNode(preorder[0]); Deque stack = new ArrayDeque<>(Arrays.asList(root)); for (int i = 1; i < preorder.length; ++i) { TreeNode parent = stack.peek(); TreeNode child = new TreeNode(preorder[i]); // Adjust parent while (!stack.isEmpty() && stack.peek().val < child.val) parent = stack.pop(); // Create parent-child link according to BST property if (parent.val > child.val) parent.left = child; else parent.right = child; stack.push(child); } return root; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 class Solution: def bstFromPreorder(self, preorder: List[int]) -> Optional[TreeNode]: root = TreeNode(preorder[0]) stack = [root] for i in range(1, len(preorder)): parent = stack[-1] child = TreeNode(preorder[i]) # Adjust parent while stack and stack[-1].val < child.val: parent = stack.pop() # Create parent-child link according to BST property if parent.val > child.val: parent.left = child else: parent.right = child stack.append(child) return root