1008. Construct Binary Search Tree from Preorder Traversal LeetCode Solution

In this guide, you will get 1008. Construct Binary Search Tree from Preorder Traversal LeetCode Solution with the best time and space complexity. The solution to Construct Binary Search Tree from Preorder Traversal problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Construct Binary Search Tree from Preorder Traversal solution in C++
Construct Binary Search Tree from Preorder Traversal solution in Java
Construct Binary Search Tree from Preorder Traversal solution in Python
Additional Resources

1008. Construct Binary Search Tree from Preorder Traversal LeetCode Solution image

Problem Statement of Construct Binary Search Tree from Preorder Traversal

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.

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(h)

1008. Construct Binary Search Tree from Preorder Traversal LeetCode Solution in C++

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 the 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;
  }
};
/* code provided by PROGIEZ */

1008. Construct Binary Search Tree from Preorder Traversal LeetCode Solution in Java

class Solution {
  public TreeNode bstFromPreorder(int[] preorder) {
    TreeNode root = new TreeNode(preorder[0]);
    Deque<TreeNode> stack = new ArrayDeque<>(List.of(root));

    for (int i = 1; i < preorder.length; ++i) {
      TreeNode parent = stack.peek();
      TreeNode child = new TreeNode(preorder[i]);
      // Adjust the 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;
  }
}
// code provided by PROGIEZ

1008. Construct Binary Search Tree from Preorder Traversal LeetCode Solution in Python

class Solution:
  def bstFromPreorder(self, preorder: list[int]) -> TreeNode | None:
    root = TreeNode(preorder[0])
    stack = [root]

    for i in range(1, len(preorder)):
      parent = stack[-1]
      child = TreeNode(preorder[i])
      # Adjust the 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
 # code by PROGIEZ