DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

Prashant Mishra
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) {
        // 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);

            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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);
    }
Enter fullscreen mode Exit fullscreen mode

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;
    }
Enter fullscreen mode Exit fullscreen mode

Top comments (0)

Hi!I'm Noah!

Hey, my name is Noah and I’m the one who set up this ad!


My job is to get you to join DEV, so if you fancy doing me a favor, I’d love for you to create an account.
Β 
If you found DEV from searching around, here are a couple of our most popular articles on DEV: