CareerCup_4.6 - Get successor nodes

TreeNodeSuccessor.java

package Chapter4;


public class TreeNodeSuccessor {
    public static <T extends Comparable<T>> TreeNode<T> successor(TreeNode<T> node) {
	if(node == null) return null;
	TreeNode<T> cur;
	if(node.right != null) {
	    cur = node.right;
	    while(cur.left != null)
		cur = cur.left;
	    return cur;
	} else {
	    cur = node;
	    while(cur.parent != null) {
		if(cur.parent.left == cur)
		    return cur.parent;
		cur = cur.parent;
	    }
	}
	return null;
    }
    
    public static void main(String[] args) {
	/*	_______7______
	       /              \
	    __2__          __11
	   /     \        /
	   1      3      10
	           \    /
	            4  8 		*/
	Integer[] pre2 = { 7, 2, 1, 3, 4, 11, 10, 8 };
	Integer[] in2 = { 1, 2, 3, 4, 7, 8, 10, 11 };
	BinaryTree<Integer> bst = BinaryTreeBuilder.buildTree(pre2, in2);
	TreeNode<Integer> Node_7 = bst.root();
	TreeNode<Integer> Node_2 = bst.root().left;
	TreeNode<Integer> Node_4 = bst.root().left.right.right;
	TreeNode<Integer> Node_11 = bst.root().right;
	
	System.out.println("2's successor is " + successor(Node_2).key);
	System.out.println("4's successor is " + successor(Node_4).key);
	System.out.println("7's successor is " + successor(Node_7).key);
	System.out.println("11's successor is " + successor(Node_11));
    }
}