285. Inorder Successor in BST.md

285. Inorder Successor in BST

• if node has right subtree.
• go to very left of the right subtree
• if no right subtree:
• traversal to see the least greater parent.

Python

class Solution:
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
        if not p or not root:
            return None
        #if has right subtree, go to very left of the right subtree
        if p.right:
            p = p.right
            while p.left:
                p = p.left
            return p
        # traversal to see the least greater parent. 
        else:
            successor = None
            while(root != p):
                if root.val > p.val:
                    successor = root
                    root = root.left
                else:
                    root = root.right
            return successor

Can be simplied to:

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