Data-Structures---Algorithms/Largest BST at main · uditbhaskar21/Data-Structures---Algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public static class BSTPair{
      boolean isBST;
      int min;
      int max;
      Node root;
      int size;
  }
  public static BSTPair isBST(Node node){
      if(node==null){
          BSTPair bp = new BSTPair();
          bp.min = Integer.MAX_VALUE;
          bp.max = Integer.MIN_VALUE;
          bp.isBST = true;
          bp.size=0;
          bp.root=node;
          return bp;
      }
      BSTPair lp = isBST(node.left);
      BSTPair rp = isBST(node.right);
      BSTPair mp = new BSTPair();
      mp.isBST = lp.isBST && rp.isBST &&(node.data>=lp.max && node.data<=rp.min);
      mp.min=Math.min(node.data,Math.min(lp.min,rp.min));
      mp.max = Math.max(node.data,Math.max(lp.max,rp.max));

      if(mp.isBST){
          mp.root = node;
          mp.size = lp.size+rp.size+1;
      }else if(lp.size>rp.size){
          mp.root = lp.root;
          mp.size = lp.size;
      }else{
          mp.root = rp.root;
          mp.size = rp.size;
      }


      return mp;
  }