BST
Wed Jan 11 2023 13:07:47 GMT+0000 (Coordinated Universal Time)
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); } }
Comments