285. Inorder Successor in BST (Medium) - TengnanYao/daily_leetcode GitHub Wiki

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'Optional[TreeNode]':
        # shortest
        result = None
        while root:
            if p.val >= root.val:
                root = root.right
            else:
                result = root
                root = root.left
        return result
    
        # optimized
        if p.right:
            p = p.right
            while p.left:
                p = p.left
            return p
        result = None
        while root.val != p.val:
            if root.val > p.val:
                result = root
                root = root.left
            else:
                root = root.right
        return result
            
        # brute force: save all nodes
        arr = []
        nodes = []
        def dfs(root):
            if root:
                dfs(root.left)
                arr.append(root.val)
                nodes.append(root)
                dfs(root.right)
        dfs(root)
        i = arr.index(p.val)
        if i == len(arr) - 1:
            return None
        return nodes[i + 1]