#ctci

NextSuccessor.java

// it is always doable to just XX-order traverse the whole tree and save them somewhere 
// if we have the root and then find the next node of our target node.
//
// however, in this question we are only given the target node and we know that we have
// node back to its parent. I guess we have to work from there.
// 
// if the target node has a right child, then its in-order successor is just the first node
// without a left child in the target node's right sub tree.
//
// the tricky part is when the target node has no right child.
// at first glance it seems easy, just return its parent and we are done right?
// well not quite. If the target node is its parent's left child, then we can return the parent.
// but what if it's the right child of its parent?
// if we draw graph here we can see that we have to go up the parent link of the target node 
// until we find the first node that is its parent's left child. Then we return that node's parent.
//      50
// 45
//   46
//       47
//         48
// so for node 48, the next node is 50.
//
// Assume that we have the following node class
// public class Node{
//     int val;
//     Node left;
//     Node right;
//     Node parent;
// }
public class NextNode{
    public Node getNextNode(Node target){
        if(target == null) return null;
        
        // target has a right child
        if(target.right != null) return min(target.right);
        
        // target has no right child and is the left child of its parent.
        // Note that actually we do not need this line here 
        // since it is covered by the part below.
        // but since this is how we thought through the problem, it makes the process clearer.
        if(target == target.parent.left) return target.parent;
        
        // target has no right child and is its parent's right child
        while(target == target.parent.right) target = target.parent;
        return target.parent;
    }
    
    private Node min(Node node){
        while(node.left != null) node = node.left;
        return node;
    }
}