285. Inorder Successor in BST

Given a binary search tree and a node in it, find the in-order successor of that node in the BST.

Note: If the given node has no in-order successor in the tree, return null.

Example 1:

Input: root = [2,1,3], p = 1

  2
 / \
1   3

Output: 2

Example 2:

Input: root = [5,3,6,2,4,null,null,1], p = 6

      5
     / \
    3   6
   / \
  2   4
 /   
1

Output: null

Naive implementation:

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

class Solution(object):
    def inorderSuccessor(self, root, p):
        """
        :type root: TreeNode
        :type p: TreeNode
        :rtype: TreeNode
        """
        if not root:
            return None
        traverse = []
        self.inOrder(root, traverse)
        
        if traverse[-1] == p:
            return None
        
        for i in range(len(traverse) - 1):
            if traverse[i] == p:
                return traverse[i + 1]
        
        return None
        
    def inOrder(self, root, traverse):
        if not root:
            return
        self.inOrder(root.left, traverse) # don't forget tO pass all parameters to the function
        traverse.append(root)
        self.inOrder(root.right, traverse) # don't forget tO pass all parameters to the function

Iterative (Fast):

class Solution(object):
    def inorderSuccessor(self, root, p):
        """
        :type root: TreeNode
        :type p: TreeNode
        :rtype: TreeNode
        """
        successor = None
        current = root
        while current:
            if p.val < current.val:
                successor = current
                current = current.left
            else:
                current = current.right
        return successor

Recursive (Faster):

class Solution(object):
    def inorderSuccessor(self, root, p):
        """
        :type root: TreeNode
        :type p: TreeNode
        :rtype: TreeNode
        """
        def recursive(root, p, successor):
            if not root:
                return successor # 当 root 是 根 的 None 时，返回这个传进来的这个最小的比 target 大的值
            elif p.val < root.val:
                return recursive(root.left, p, root) # 传入目前为止最小的比 target 大的值
            else:
                return recursive(root.right, p, successor) # 传入目前为止最小的比 target 大的值
        successor = None # 默认 maxInt 的 node 是 None
        return recursive(root, p, successor)

做 recursive 的 tree 题时，想象把每一个大 🍰 切分成可用相同方法处理的小 🍰；每次只思考小 🍰 的处理方法即可写出 recursive 的步骤。最终停止在 node 为 None 这个最小的 🍰 上。