Successor and Predecessor

The inorder successor of a node is the next node in sorted order. The predecessor is the previous.

Finding successor:

$1.$ If node has right child: successor is leftmost node in right subtree

$2.$ 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: $O(h)$.