Leetcode 1008: Construct Binary Search Tree from Preorder Traversal

Input: The input consists of an array of integers representing the preorder traversal of a BST. The array will have a length of at least 1 and at most 100, with each integer between 1 and 1000.

Example: preorder = [10, 5, 1, 7, 15, 12]

Constraints:

• 1 <= preorder.length <= 100

• 1 <= preorder[i] <= 1000

• All elements in the preorder array are unique.

Output: Return the root of the binary search tree constructed from the given preorder traversal.

Example: Output: [10,5,15,1,7,null,12]

Constraints:

• The output is the root of the binary search tree in level-order traversal.

Goal: The goal is to construct a binary search tree from the preorder traversal. Each node in the tree should satisfy the BST property where the left child is less than the parent and the right child is greater than the parent.

Steps:

• Start with the first element of the preorder array as the root of the tree.

• For each subsequent element, place it in the correct position in the tree following the BST rules.

• Continue this process until all elements are placed in the tree.

Goal: Ensure the solution can handle up to the maximum constraint efficiently.

Steps:

• The preorder array will always have at least one element and at most 100 elements.

Assumptions:

• The preorder array contains unique values and forms a valid BST.

• Input: Input: preorder = [10, 5, 1, 7, 15, 12]

• Explanation: In this case, we can construct the following BST: [10, 5, 15, 1, 7, null, 12]. The first element 10 becomes the root, then 5 goes to the left of 10, 1 goes to the left of 5, and so on.

• Input: Input: preorder = [15, 10, 5, 12, 20, 17]

• Explanation: For this input, the BST would look like [15, 10, 20, 5, 12, null, 17]. Starting with 15 as the root, 10 goes to the left, 20 goes to the right, and so on.

Approach: We can use the preorder traversal of a BST to reconstruct the tree. We start with the first element as the root and use the properties of BSTs to place each subsequent element in the correct position.

Observations:

• We need to ensure that each element is inserted in the correct position based on the BST rules.

• The key idea is to use a recursive approach to insert nodes into the tree while maintaining the BST property.

Steps:

• 1. Start with the first element in the preorder array as the root of the tree.

• 2. Use a helper function to recursively insert each element into the tree based on the BST property (left < node < right).

• 3. Ensure that for each recursive call, the current node value is within the allowed bounds, which change based on the parent node's value.

Empty Inputs:

• The input array will never be empty, as per the problem constraints.

Large Inputs:

• The solution should be optimized to handle the maximum input size (up to 100 elements).

Special Values:

• If all values are large (e.g., all greater than 500), the BST structure should still be correct.

Constraints:

• The input array will always contain unique values, so there is no need to handle duplicates.

class Solution {
int i = 0;
public:
TreeNode* bstFromPreorder(vector<int>& pre, int bound = INT_MAX) {
    if(i == pre.size() || pre[i] > bound) return NULL;
    
    TreeNode* root = new TreeNode(pre[i++]);
    root->left = bstFromPreorder(pre, root->val);
    root->right = bstFromPreorder(pre, bound);
    return root;
}

1 : Class Declaration

class Solution {

Declares a Solution class to house the method for building the BST from the preorder traversal.

2 : Variable Initialization

int i = 0;

Initializes a class member variable i to track the current index in the preorder vector while recursively constructing the BST.

3 : Access Specifier

public:

Specifies that the following members are public and can be accessed from outside the class.

4 : Function Declaration

TreeNode* bstFromPreorder(vector<int>& pre, int bound = INT_MAX) {

Declares the function `bstFromPreorder` which takes a vector of integers `pre` (representing the preorder traversal of a BST) and an optional `bound` parameter to limit node values during recursion.

5 : Base Case

    if(i == pre.size() || pre[i] > bound) return NULL;

Checks if the current index has reached the end of the preorder vector or if the current node value exceeds the allowed bound, indicating that no more nodes can be added under this subtree.

6 : Node Creation

    TreeNode* root = new TreeNode(pre[i++]);

Creates a new TreeNode with the current value from the preorder vector and increments the index i.

7 : Left Subtree Construction

    root->left = bstFromPreorder(pre, root->val);

Recursively constructs the left subtree by passing the current node's value as the new bound, ensuring that the left child is smaller than the current node.

8 : Right Subtree Construction

    root->right = bstFromPreorder(pre, bound);

Recursively constructs the right subtree with the original bound, ensuring that the right child is larger than the current node.

9 : Return Statement

    return root;

Returns the root of the current subtree.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n^2)

Description: The time complexity is O(n) in the best case when the tree is balanced, but it can be O(n^2) in the worst case when the tree is skewed (e.g., a sorted array).

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) due to the recursion stack and the space used to store the tree.

Leetcode 1008: Construct Binary Search Tree from Preorder Traversal

Explore →