Skip to Main Content

Java Programming

Announcement

For appeals, questions and feedback about Oracle Forums, please email oracle-forums-moderators_us@oracle.com. Technical questions should be asked in the appropriate category. Thank you!

BST: Finding the second smallest item in the tree...

807606Mar 28 2007 — edited Mar 31 2007
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;
	}

}
Comments
Locked Post
New comments cannot be posted to this locked post.
Post Details
Locked on Apr 28 2007
Added on Mar 28 2007
17 comments
956 views