The inorder successor of a node is the next node in sorted order. The predecessor is the previous.
Finding successor: If node has right child: successor is leftmost node in right subtree
Otherwise: go up until you find a node that is a left child of its parent; that parent is the successor
def successor(root, p):
succ = null
while root:
if p.val < root.val:
succ = root
root = root.left
else:
root = root.right
return succ
This works without parent pointers. You track the last node where we went left—that's the successor. Time: .