# 285. Inorder Successor in BST

{%hackmd theme-dark %}
Given the root of a binary search tree and a node p in it, return the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null.

The successor of a node p is the node with the smallest key greater than p.val.

> p existing
> node v is unique
> 4
> 2 6
> 1 3 5 7

>1. to inorde arr [1 2 3 4 5 6 7] find p=6 return next

>2. p = 6
> 4 -> 6 has right and return left most
>3. p= 3
> 4 -> 2 -> 3 has no children

> p = 6
> 4 -> 6 -> 7* -> left = 7
> p = 3
> 4* -> 2 -> 3 -> right = 4

SC O(1)
TC O(N) N: node count

def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
    
    #p = 6 
    #p = 3
    # edge case and init
    self.ans = TreeNode(inf)
    
        # helper traverse
        def helper(node):
            if not node: 
                return

            val = node.val #4, 2, 3
            if p.val < val < self.ans.val:
                self.ans = node # 4

            if val <= p.val: #
                helper(node.right) # n3
            else:
                helper(node.left) # n2

        # ans
        helper(root)
        if self.ans.val == inf:
            return None
        return self.ans

    
    successor = None
        while root:
            if root.val > p.val:
                successor = root
                root = root.left
            else:
                root = root.right
        
        return successor

>
>[5,3,6,2,4,null,null,1]
>1

###### tags: `mock interview` `面試`