I'm having some troubles writing the "secondSmallest" method that returns the value of the second smallest item in a binary search tree. What I have now works for what few test cases it has been run through, although it seems rather silly that I'm using two auxiliary methods. Is there a more elegant approach to this, or at least an obvious way to remove the auxiliary methods? I'm trying to do this recursively in some shape or form, so I should be following the base / recursive case formula, but I'm having problems getting those cases nailed down, thus the code that follows. Anyway, enough rambling and onto the business end of this post...
Here's what I currently have:
public static Comparable secondSmallest(BSTreenode T) {
if (T == null)
return null;
if (T.getData() == null)
return null;
if (T.getLeft() == null && T.getRight() == null)
return null;
if (T.getLeft() != null && T.getLeft().getRight() == null
&& T.getLeft().getLeft() == null)
return T.getData();
if (T.getRight() != null && T.getRight().getLeft() == null) {
return T.getRight().getData();
}
if (T.getLeft() != null)
return lsecondSmallest(T.getLeft());
return rsecondSmallest(T.getRight());
}
public static Comparable lsecondSmallest(BSTreenode T) {
if (T.getLeft() == null)
return rsecondSmallest(T.getRight());
if (T.getLeft().getLeft() != null)
return lsecondSmallest(T.getLeft());
return rsecondSmallest(T.getRight());
}
public static Comparable rsecondSmallest(BSTreenode T) {
if (T.getLeft().getLeft() != null)
return rsecondSmallest(T.getLeft());
return T.getLeft().getData();
}
And here's the BSTreenode class to go with it:
public class BSTreenode {
// fields
private Comparable data;
private BSTreenode left, right;
public BSTreenode() {
data = null;
left = null;
right = null;
}
public BSTreenode(Comparable c, BSTreenode l, BSTreenode r) {
data = c;
left = l;
right = r;
}
public BSTreenode(Comparable c) {
data = c;
left = null;
right = null;
}
// methods
public Comparable getData() {
return data;
}
public BSTreenode getLeft() {
return left;
}
public BSTreenode getRight() {
return right;
}
public void setLeft(BSTreenode l) {
left = l;
}
public void setRight(BSTreenode r) {
right = r;
}
}