/*
1. 中序后继点可以分为3种情况讨论,
1.2 后继节点在node 上方:   
    father.left == node -> father
    father.right == node ->  node = father 递归寻找
1.3 后继节点在node 下方:
    右子树的最左叶子节点

1.4 无后继


2. 
2.1 :1.2, 1.3 要独立判断, 后面需要判断是独立if 还是 互斥的if-else
2.2 : 看来大多数mid 题目都能分情况讨论

*/

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node parent;
};
*/
class Solution {
    public Node inorderSuccessor(Node node) {
        Node candidate = null;
        if (node.parent != null){
            Node p = node;
            while (p.parent != null && p.parent.right == p) p = p.parent;
            if (candidate == null || p.parent.val < candidate.val){
                candidate = p.parent;
            }
        } 
        if (node.right != null){
            Node p = node.right;
            while (p.left != null) p = p.left;
            if (candidate == null || p.val < candidate.val){
                candidate = p;
            }
        }

        return candidate;
    }
}