Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

1008. Construct Binary Search Tree from Preorder Traversal

Time: $O(n)$

Space: $O(h)$

			


class Solution {
 public:
  TreeNode* bstFromPreorder(vector<int>& preorder) {
    TreeNode* root = new TreeNode(preorder[0]);
    stack<TreeNode*> 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;
  }
};




			


class Solution {
  public TreeNode bstFromPreorder(int[] preorder) {
    TreeNode root = new TreeNode(preorder[0]);
    Deque<TreeNode> 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;
  }
}




			


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