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;
}