The successor of a node is the next visited node in inorder traversal. So it's either its parent or the left most leaf of its right subtree. So we could get the result by the following algorithm.
First, do a binary search and get the node p. While we do this binary search, we should always save the parent node of current node.
Once we get the node p, we could get the successor of the node by following way. If its right node is None, the successor if its parent. If its right node is not None, it's successor is the left most leaf of its right sub-tree.
# 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': parent = None node = root while node and node != p: if node.val < p.val: node = node.right else: parent = node node = node.left if node is None: return None if node.right is None: return parent else: successor = node.right while successor.left: successor = successor.left return successor