# 285 Inorder Successor in BST

Concept: Inorder successor就是用inorder traverse tree時，p的下一個treenode。

inorder travers BST時，會由小排到大。

先在root中找到p的位置，p若是left child of some node，就要回傳p的parent。

p若是right child，就要回傳p的parent的parent。

p若有right child，就要回傳right subtree下面最小的leaf。

Code:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode suc = null;
        while(root!=null){
            if(p.val<root.val){
                suc = root;
                root = root.left;
            }
            else
                root = root.right;
        }
        return suc;
    }
}