Inorder Successor in BST

题目地址：
https://leetcode.com/problems/inorder-successor-in-bst/#/description

题目：

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

解题思路：
这道题的主要解法是recursion，需要判断的点是当前node的val和p的val的大小。然后还会有follow up：如果是找predecessor的话，稍微修改一下代码就好。最后一个是将recursion改为iteration。

代码：

successor：

public TreeNode successor(TreeNode root, TreeNode p) {
    if (root == null)
        return null;

    if (root.val <= p.val) {
        return successor(root.right, p);
    } else {
        TreeNode left = successor(root.left, p);
        return (left != null) ? left : root;
    }
}

 predecessor:

public TreeNode predecessor(TreeNode root, TreeNode p) {
    if (root == null)
        return null;

    if (root.val >= p.val) {
        return predecessor(root.left, p);
    } else {
        TreeNode right = predecessor(root.right, p);
        return (right != null) ? right : root;
    }
}

iteration version of successor：

public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
    if(root == null){
        return null;
    }
    while(root != null && root.val <= p.val){
        root = root.right;
    }
    if(root == null){
        return null;
    }
    TreeNode left = inorderSuccessor(root.left, p);
    return left != null ? left : root;
}