[LeetCode] 285. Inorder Successor in BST

 Problem : https://leetcode.com/problems/inorder-successor-in-bst/

The recursive approach:

# 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') -> 'TreeNode':
        self.pre = None
        
        def inorder(node):
            if node:
                tmp = inorder(node.left)
                if tmp: return tmp
                
                if self.pre == p:
                    return node
                
                self.pre = node
                
                tmp = inorder(node.right)
                if tmp: return tmp
        
        return inorder(root)

The iterative approach:

# 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') -> 'TreeNode':
        pre = None
        stack = [root]
        
        while stack:
            node = stack[-1]
            
            while node.left:
                stack.append(node.left)
                left = node.left
                node.left = None
                node = left
            
            node = stack.pop()
            if pre == p: 
                return node
            
            pre = node
            
            if node.right:
                stack.append(node.right)
                node.right = None

However the previous 2 approaches do not leverage BST properties.

We can safely discard the left sub-tree, if root.val <= p.val

# 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') -> 'TreeNode':
        
        result = None
        
        while root:
            if p.val >= root.val:
                root = root.right
            else:
                result = root
                root = root.left
    
        return result