Prashant Mishra

Posted on

# 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) {
// we will use level order traversal for this
if(root==null) return;
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;

}
}
}
}
``````

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];
for(int i =0;i< sortedArray.length;i++){
sortedArray[i] = 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;
}
``````