Problem

The problem requires us to construct a Binary Search Tree (BST) from a given Preorder traversal.

A Preorder Traversal of a binary tree is a traversal in which we first visit the root, then the left subtree, and finally the right subtree.

In the context of a Binary Search Tree (BST), all values in the left subtree of a node must be smaller than the node's value and all values in the right subtree must be larger.

Given these conditions, we can see that in a Preorder traversal of a BST, the first value is the root of the BST, and the subsequent values are divided into two segments: the first segment contains values smaller than the root (left subtree) and the next segment contains values larger than the root (right subtree).

Example

For example, given an input [8,5,1,7,10,12], the output would be [8,5,10,1,7,null,12]. Here, 8 is the root, values [5,1,7] forms the left subtree and [10,12] forms the right subtree.

Approach

The solution is designed to follow this same logic using a stack to maintain the BST property and keep track of the nodes.

1. The precondition for the problem is that the given array length must be between 1 and 100, and all elements in the array are distinct. The first element of the array represents the root of the BST.

2. We create a new node with root value and add it to the stack.

3. We run a loop starting from the second element in the array. For each value, we create a new node and assign the top of the stack as its parent node.

4. We check and pop the stack while the top of the stack has a value less than the current node's value and update the parent node.

5. If the parent node's value is more than the current node's value, we make it the left child of the parent. Otherwise, it becomes the right child of the parent.

6. We then push the current node to the stack.

7. After traversing all elements, we return the root node.

Python Solution

1
2python
3class Solution:
4    def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
5        root = TreeNode(preorder[0])
6        stack = [root]
7        
8        for value in preorder[1:]:
9            node = TreeNode(value)
10            if value < stack[-1].val:
11                stack[-1].left = node
12            else:
13                while stack and stack[-1].val < value:
14                    last = stack.pop()
15                last.right = node
16            stack.append(node)
17        return root

Java Solution

1
2java
3class Solution {
4    int i=0;
5    public TreeNode bstFromPreorder(int[] preorder) {
6        return build(preorder, Integer.MAX_VALUE);
7    }
8
9    TreeNode build(int[] preorder, int bound){
10        if(i==preorder.length || preorder[i]>bound) return null;
11        TreeNode root = new TreeNode(preorder[i++]);
12        root.left = build(preorder, root.val);
13        root.right = build(preorder, bound);
14        return root;
15    }
16}

Javascript Solution

1
2javascript
3var bstFromPreorder = function(preorder) {
4    return dfs(Infinity);
5    
6    function dfs(ub) {
7        if (preorder[0] > ub) return null; 
8        const root = new TreeNode(preorder.shift());
9        root.left = dfs(root.val);
10        root.right = dfs(ub);
11        return root;
12    }
13};

C++ Solution

1
2cpp
3class Solution {
4public:
5   TreeNode* bstFromPreorder(vector<int>& preorder) {
6       return helper(preorder, INT_MAX);
7   }
8   
9   int idx = 0;
10   TreeNode* helper(vector<int>& preorder, int bound) {
11       if (idx == preorder.size() || preorder[idx] > bound) 
12           return NULL;
13       TreeNode* root = new TreeNode(preorder[idx++]);
14       root->left = helper(preorder, root->val);
15       root->right = helper(preorder, bound);
16       return root;
17   }
18};

C# Solution

1
2csharp
3public class Solution {
4    int idx = 0;
5    int[] preorder;
6    int n;
7
8    public TreeNode BstFromPreorder(int[] preorder) {
9        this.preorder = preorder;
10        n = preorder.Length;
11        return BstFromPreorder(int.MaxValue);
12    }
13
14    public TreeNode BstFromPreorder(int bound) {
15        if (idx == n || preorder[idx] > bound)
16            return null;
17
18        TreeNode node = new TreeNode(preorder[idx++]);
19        node.left = BstFromPreorder(node.val);
20        node.right = BstFromPreorder(bound);
21        
22        return node;
23    } 
24}

These solutions work by creating the Binary Search Tree from the given preorder traversal by using stack and recursion. Each distinct programming language solution handles the base cases and recursion in a slightly different way, but follows the same approach overall.

It's important to note:

In Python, a list is used to imitate a stack. The last value in the list (stack[-1]) is being used to represent the top of the stack since Python does not have a built-in stack data structure.

In Java, C++, and C# solutions, we use recursive function to build left and right subtree. This solutions utilize a global index to keep track of the preorder array.

In Javascript, an upper bound ub is defined that is initially given an Infinity value. The dfs function then runs until the value pulled from the preorder array exceeds this bound, at which point it returns null and ends the function.

I hope these solutions helped you understand better how to construct Binary Search Trees from Preorder Traversals! Remember, practice is key, and happy coding!