# 0510. Inorder Successor in BST II
###### tags: `Leetcode` `Medium` `FaceBook` `Tree Traversal`
Link: https://leetcode.com/problems/inorder-successor-in-bst-ii/
## 思路
如果当前node的right child不是空，就正常按照iterative inorder traversal的方式，找到right child的left most child然后返回
如果当前node的right child是空，那么就以为着我们要往上找，直到找到一个node，发现当前node在它的左子树里面，则返回当前node
## Code

class Solution {
    public Node inorderSuccessor(Node node) {
        if(node.right!=null){
            Node curr = node.right;
            while(curr.left!=null){
                curr = curr.left;
            }   
            return curr;
        }
        else{
            Node curr = node;
            while(curr.parent!=null && curr.parent.right==curr){
                curr = curr.parent;
            }
            return curr.parent;
        }
        
    }
}