GetSuccessor.java

//http://coolcodebro.blogspot.com/2012/12/find-successor-of-node.html

TreeNode getSuccessor(TreeNode node) {
	TreeNode n;
	
	//Case 1: node has a right child
	if(node.right != null) {
		n = node.right;
		while(n.left != null)
			n = n.left;
		
		return n;
	}
	
	//Case 2: node does not have a right child
	n = node.parent;
	while(n != null && n.right == node) {
		node = n;
		n = node.parent;
	}
	
	return n;
}