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.

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.

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] <= 108
  • All the values of preorder are unique.

Efficient Solutions by OpHaxor:

public TreeNode bstFromPreorder(int[] pre) {
    return construct(pre,0,pre.length-1);
}

private static TreeNode construct(int pre[],int start,int end) {
    if(start>end) {
        return null;
    }
  
    TreeNode root=new TreeNode(pre[start]);

    for(int i=start+1;i<=end;i++) {
        if(pre[i]>root.val)
        break;
     }
     
     root.left=construct(pre,start+1,i-1);
     root.right=construct(pre,i,end);

     //return the root
     return root;
}
def bstFromPreorder(self, preorder: List[int]) -> TreeNode:
        def insert(head,val):
            prev = head
            while head:
                prev = head
                if val<head.val:
                    head = head.left
                else:
                    head = head.right
            
            if val<prev.val:
                prev.left = TreeNode(val)
            else:
                prev.right = TreeNode(val)
            
        head = TreeNode(preorder[0])        
        
        for i in range(1,len(preorder)):
            node = preorder[i]
            insert(head,node)
        
        return head
            
        
        
public:
    TreeNode* bstFromPreorder(vector<int>& preorder) {
        return helper(preorder, 0, INT_MAX).first;
    }
    
    pair<TreeNode*, int> helper(vector<int>& nums, int start, int bound) {
        if (start == nums.size() || (nums[start] >= bound))
            return {NULL, start};
        TreeNode* root = new TreeNode(nums[start]);
        auto l = helper(nums, start+1, root->val);
        root->left = l.first;
        auto r = helper(nums, l.second, bound);
        root->right = r.first;
        return {root, r.second};
    }

Leave a reply