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.

Approach 1:


class Solution {
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null)
            return new TreeNode(val);
        else if (root.val > val)
            root.left = insertIntoBST(root.left, val);
        else
            root.right = insertIntoBST(root.right, val);
        return root;
    }

    public TreeNode bstFromPreorder(int[] preorder) {
        TreeNode root = new TreeNode(preorder[0]);
        for (int i = 1; i < preorder.length; i++) {
            root = insertIntoBST(root, preorder[i]);
        }
        return root;
    }
}

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

The problem "Construct Binary Search Tree from Preorder Traversal" involves constructing a binary search tree (BST) given its preorder traversal. Preorder traversal visits nodes in the order: root, left subtree, right subtree. The challenge is to use this traversal to build the tree while ensuring the properties of a binary search tree are maintained.

In a Binary Search Tree, for each node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This constraint allows us to efficiently insert values as we traverse the preorder array.

Problem Statement

Given an array `preorder` representing the preorder traversal of a binary search tree, construct the BST and return its root. It is guaranteed that the input represents a valid BST.

The tree node structure is given above. We need to reconstruct the binary search tree from the provided preorder traversal.

Approach

The key insight for this problem is that the preorder traversal array gives us the nodes in the order they are visited. Since it's a binary search tree, we can insert the elements into the tree one by one while maintaining the BST property:

The first element in the preorder array is the root of the tree or subtree.
The subsequent elements that are less than the root will be placed in the left subtree, and those greater than the root will be placed in the right subtree.
We recursively apply this logic to construct the left and right subtrees for each node.

To efficiently construct the tree, we can use a helper function that will take the current node's value and an upper and lower bound. This bound ensures that the inserted nodes maintain the BST property during the recursive construction process.

Algorithm

The algorithm for constructing the BST from preorder traversal can be described as follows:

Start with the first element in the preorder array as the root.
For each subsequent element, check if it can be inserted into the left or right subtree based on the BST property.
Use recursion to insert each node into the appropriate subtree while maintaining the BST property.
Continue until all nodes from the preorder traversal are inserted into the tree.

A key point is that the preorder array is processed in sequence, and each node's insertion is bounded by the range of valid values for its position in the tree.

Example

Consider the following preorder traversal:

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

To construct the BST: - The first element is 8, which is the root. - 5 is less than 8, so it goes to the left of 8. - 1 is less than 5, so it goes to the left of 5. - 7 is greater than 5 but less than 8, so it goes to the right of 5. - 10 is greater than 8, so it goes to the right of 8. - 12 is greater than 10, so it goes to the right of 10.

        Tree:
                8
               / \
              5   10
             / \    \
            1   7    12

The binary search tree is successfully reconstructed with 8 as the root, and the subsequent elements inserted into the tree according to the BST properties.

Code Implementation

Below is the Python implementation of the algorithm to construct the BST from preorder traversal:

In this code: - The function `bstFromPreorder` initializes the recursion by calling the `construct` helper function. - The `construct` function builds the tree recursively by ensuring that each node is inserted in the correct position within the bounds (defined by the `lower` and `upper` parameters). - The preorder array is used to get the current node's value, and the tree is built by recursively inserting nodes in the left and right subtrees.

Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the tree. Each node is processed once during the recursive calls, and the insertion of each node takes constant time.

The space complexity is O(n), where n is the number of nodes in the tree. This is due to the space used by the recursion stack, as the tree is constructed recursively. The space used by the preorder array is also considered.

Conclusion

The "Construct Binary Search Tree from Preorder Traversal" problem is an excellent exercise in recursion and understanding binary search trees. By leveraging the preorder traversal array, we can efficiently build the binary search tree while maintaining its properties. This problem helps improve skills in tree construction and traversal techniques.