BST

PHOTO EMBED

Wed Jan 11 2023 13:07:47 GMT+0000 (Coordinated Universal Time)

Saved by @Beluga #java 

import java.util.ArrayList;

public class BST extends Trees{
    static ArrayList<Integer> arr=new ArrayList<>();
    public static node insert(int val, node root){
        if(root==null){
            root=new node(val);
            return root;
        }
        if(val<root.data)
            root.left=insert(val,root.left);
        else
            root.right = insert(val,root.right);
        return root;
    }

    public static void inorder(node root){
        if(root==null) return;
        inorder(root.left);
        System.out.print(root.data +" ");
        inorder(root.right);
    }

    public static boolean find(node root, int val){
        if(root==null) return false;
        if(root.data==val) return true;
        if(val> root.data) return find(root.right,val);
        else return find(root.left,val);
    }

    public static node delete(node root, int val){
        if (root.data < val) root.right=delete(root.right,val);
        else if(root.data > val) root.left=delete(root.left,val);
        else {
            if(root.left==null && root.right==null){
                return null;
            }
            if(root.left==null) return root.right;
            else if(root.right==null) return root.left;
            else{
                node inorderSuccessor=findInorderSuccessor(root.right);
                root.data=inorderSuccessor.data;
                root.right=delete(root.right,inorderSuccessor.data);
            }
        }
        return  root;
    }
    public static node findInorderSuccessor(node root){
        while(root.left!=null){
            root=root.left;
        }
        return root;
    }

    public static void printInRange(node root, int k1, int k2){
        if(root==null) return ;
        if(root.data>=k1 && root.data<=k2){
            printInRange(root.left,k1,k2);
            System.out.print(root.data+" ");
            printInRange(root.right,k1,k2);
        }
        else if(root.data<k1) printInRange(root.right,k1,k2);
        else printInRange(root.left,k1,k2);
    }

    public static void printRoot2Leaf(node root, ArrayList<Integer> path){
        if(root==null) return;
        path.add(root.data);
        if(root.left==null && root.right==null)
            System.out.println(path);
        printRoot2Leaf(root.left,path);
        printRoot2Leaf(root.right,path);
        path.remove(path.size()-1);
    }

    public static boolean isValidBST(node root){
        INORDER(root);
        for(int i=0;i<arr.size()-1;i++){
            if(arr.get(i)> arr.get(i+1)) return false;
        }
        return true;
    }
    public static void INORDER(node root){
        if(root==null) return;
        INORDER(root.left);
        arr.add(root.data);
        INORDER(root.right);
    }

    public static node createBST(int[] arr,int st, int end){  //always taking mid-value of array and making it root
        if(st>end) return null;
        int mid=(st+end)/2;
        node root=new node(arr[mid]);
        root.left=createBST(arr,st,mid-1);
        root.right=createBST(arr,mid+1,end);
        return root;
    }

    public class info {
        boolean isBST;
        int size;
        int min;
        int max;

        public info(boolean isBST, int size, int min, int max){
            this.isBST=isBST;
            this.size=size;
            this.min=min;
            this.max=max;
        }
    }
    public static int maxBST=0;
    public info largestBST(node root){
        if(root==null) return new info(true,0,Integer.MAX_VALUE,Integer.MIN_VALUE);
        info leftInfo=largestBST(root.left);
        info rightInfo=largestBST(root.right);
        int size=leftInfo.size+rightInfo.size+1;
        int min=Math.min(root.data,Math.min(leftInfo.min, rightInfo.min));
        int max=Math.max(root.data,Math.max(leftInfo.max, rightInfo.max));
        if(root.data<= leftInfo.max||root.data>= rightInfo.min) {
            return new info(false,size,min,max);
        }
        if(leftInfo.isBST && rightInfo.isBST){
            maxBST=Math.max(maxBST,size);
            return new info(true,size,min,max);
        }
        return new info(false,size,min,max);
    }

    public static void main(String[] args) {
//        int[] arr = {8,5,3,1,4,6,10,11,14};
        int[] arr={3,5,6,8,10,11,12};
        node root=createBST(arr,0, arr.length-1);
        inorder(root);
    }
}
content_copyCOPY