Construct Binary Search Tree from Preorder Traversal — LeetCode Day 24 May Challenge

So we are given a list of integers which is the preorder traversal of a binary search tree. We need to generate the binary search tree and return it.

We start of with a root node,

TreeNode root = new TreeNode(preorder[0]);

Before we get on to traversing the given list lets create a function to put every node in its right place.

In the recursive function, we first check which side the element belongs to (left/right) then we check if there is already a node present, if so we check which side the element belongs to of that node, else we create a new node.

public void generate(int element, TreeNode current){
        if ( element < current.val){    
            if ( current.left == null ){
                current.left = new TreeNode(element);
            } else{
                generate(element, current.left);
            } 
            
        } else {
            if ( current.right == null) {
                current.right = new TreeNode(element);
            } else{
                generate(element, current.right);
            }
        }     
    }

Now onto the putting the given list in the correct positions of a Binary Search Tree.

for (int i = 1; i < preorder.length; i++){
            generate(preorder[i], root);
        }

We then return the root which has the whole binary tree linked to it.

return root;

The full code looks like:

class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        
        TreeNode root = new TreeNode(preorder[0]);
for ( int i = 1; i < preorder.length; i++){
            generate(preorder[i], root);
        }   
        
        return root;
    }
    
    public void generate(int element, TreeNode current){
        if ( element < current.val){    
            if ( current.left == null ){
                current.left = new TreeNode(element);
            } else{
                generate(element, current.left);
            } 
            
        } else {
            if ( current.right == null) {
                current.right = new TreeNode(element);
            } else{
                generate(element, current.right);
            }
        }     
    } 
}

Full video explanation: