LC 0285 [M] Inorder Successor in BST - ALawliet/algorithms GitHub Wiki

consider the case:

[5,3,6,2,4,null,null,1]
1
                5
        3               6
    2       4
1
Output: 5
Expected: 2

without the check:

if not self.successor or node.val < self.successor.val

it returns 5 because though it found the 2, even if you try to return that answer early, the recursion for the right side already fired, so it will still run and find 5 and incorrectly replace the 2

# 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]':
        self.successor = None
        
        def inorder(node):
            if not node:
                return None
            
            inorder(node.left)
            
            if node.val > p.val:
                if not self.successor or node.val < self.successor.val:
                    self.successor = node
            
            inorder(node.right)
        
        inorder(root)
        
        return self.successor