Find max subtree in BST

Viewed 33

In a binary search tree, find the maximum subtree with the largest number of vertices in which, for each non-leaf vertex, the number of vertices in the left subtree is more than the number of vertices in the right subtree. LMoreThanR is a method returns the first subtree where there are more vertices in the left branch.

    boolean LMoreThanR(KjvNode t, KjvPrms1 out)  
      { boolean b = true;                        
        if (t==null) 
          {b = false; out.rFoundTree = null; out.count = 0; }
        else
          {KjvPrms1 prm_l = new KjvPrms1();
           KjvPrms1 prm_r = new KjvPrms1();
           boolean bl = LMoreThanR(t.getLeft(),prm_l);
           boolean br = LMoreThanR(t.getRight(),prm_r);
           out.count = prm_l.count + prm_r.count +1;
           if (prm_l.count > prm_r.count)
             { out.rFoundTree = t;
             }
           else if (prm_l.rFoundTree != null)
             { out.rFoundTree = prm_l.rFoundTree;                           
             }
           else 
             {b = prm_r.rFoundTree != null;
              out.rFoundTree = prm_r.rFoundTree;            
             }
          }
        
        return b;
      }
    

    public KjvNode t;   
}
class KjvPrms1 {
   
KjvNode rFoundTree;   
       int count;        
  }
0 Answers
Related