# 0285. Inorder Successor in BST
###### tags: `Leetcode` `Medium` `Binary Search Tree`
Link: https://leetcode.com/problems/inorder-successor-in-bst/
## 思路 $O(N)$ $O(1)$
非常能体现binary search tree性质的一道题
如果```root.val>p.val```说明整个root的右半部分全都可以不看了 只需要留下root的值就可以了
否则就只需要看root.right就可以了 因为root.left的subtree里面不会再有比root大的值了
## Code

class Solution:
    def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
        successor = None
        while root:
            if root.val>p.val:
                successor = root
                root = root.left
            else:
                root = root.right
        return successor

class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode successor = null;
        while(root!=null){
            if(p.val<root.val){
                successor = root;
                root = root.left;
            }
            else{
                root = root.right;
            }
        }
        return successor;
    }
}