Binary Search Tree

Populating next right pointer
TC: O(N), where N is no. of nodes in the tree

import java.util.*;
public class Solution {
    public static void connectNodes(BinaryTreeNode<Integer> root) {
        // Write your code here.
        // we will use level order traversal for this
        Queue<BinaryTreeNode<Integer>> q = new LinkedList<>();
        if(root==null) return;
        q.add(root);
        while(!q.isEmpty()){
            int size = q.size();
            BinaryTreeNode<Integer> prev = null;
            for(int i = 0;i<size;i++){
                BinaryTreeNode<Integer> node = q.remove();
                node.next= prev;
                prev = node;
                if(node.right!=null) q.add(node.right);
                if(node.left!=null)q.add(node.left);

            }
        }
    }
}

Convert Sorted Array to binary search tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.
TC: o(logn) as we are dividing the array into two equals halves which makes it same as binary search algorithm

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return createBST(0,nums.length-1,nums);
    }
    public TreeNode createBST(int start, int end,int nums[]){
        if(start > end) return null;
        int mid  = start + (end-start)/2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = createBST(start,mid-1,nums);
        node.right = createBST(mid+1,end,nums);
        return node;
    }
}

Construct preorder traversal from binary search tree
TC: O(nlogn) + O(n), where nlogn for sorting the array,

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode bstFromPreorder(int[] preorder) {
        int index =0;
        int sortedArray[] = new int[preorder.length];
        Queue<Integer> q = new LinkedList<>();
        for(int i =0;i< sortedArray.length;i++){
             sortedArray[i] = preorder[i];
             q.add(preorder[i]);
        }
        Arrays.sort(sortedArray);
        return createBst(0,sortedArray.length-1,q,sortedArray);

    }
    public TreeNode createBst(int start, int end, Queue<Integer> q,int[] sortedArray){
        if(start > end) return null;
        int rootVal = q.remove();
        TreeNode node = new TreeNode(rootVal);
        int mid = binarySearch(start,end,rootVal,sortedArray);
        node.left = createBst(start,mid-1,q,sortedArray);
        node.right = createBst(mid+1,end,q,sortedArray);
        return node;
    }
    public int binarySearch(int start, int end,int target, int[] arr){
        if(start > end) return -1;
        int mid  = start + (end-start)/2;
        if(arr[mid] == target) return mid;
        if(arr[mid] > target){
            return binarySearch(start,mid-1, target, arr);
        }
        return binarySearch(mid+1, end, target,arr);
    }

Optimized solution :
TC: O(3N) which is O(n)

//for more idea see this https://www.youtube.com/watch?v=UmJT3j26t1I
class Solution {
    public TreeNode bstFromPreorder(int preorder[]){
        return generateBST(preorder, new int[]{0},Integer.MAX_VALUE); //0 indicates the current pointer of the element that needs to be inserted
        //Integer.MAX_VALUE is max bound
    }
    public TreeNode generateBST(int[] pre,int pointer[], int bound){
        if(pointer[0] > pre.length-1 || pre[pointer[0]] > bound) return null;
        TreeNode node = new TreeNode(pre[pointer[0]++]);// value at pointer has been added to the tree, now move to next value int the array
        node.left = generateBST(pre,pointer,node.val); // now node.val will become bound for all the 
        // elements to the left of node, as they can't be equal to or greater than node.val
        node.right = generateBST(pre,pointer,bound);//for the right subtree bound will remain same
        return node;
    }