Just use the inorder traverse and keep a window/register with size 2, which keep track of two nodes just traversed.
The only critical part is
where to check the window and stop traverse.
But after you figure it out, it's quite straightforward I guess
def inorderSuccessor(self, root, p): window = [None]*2 self.inorderHelper(root, p, window) return window[-1] if window[-1] != p else None def inorderHelper(self, node, p, window): if node.left: self.inorderHelper(node.left, p, window) if window == p and window: #already find the successor! return elif window and window: #update the window window, window = window, node elif window and not window: #node is successor of root window = node else: #node is root window = node if node.right: self.inorderHelper(node.right, p, window)