public static TreeNode preorderSuccessor(TreeNode n) {
        if (n == null) return null;

        // case 1: n has a child ->
        //         just return that child (left if exists, otherwise right)
        if (n.left != null) return n.left;
        else if (n.right != null) return n.right;
        // case 2: n has no child ->
        //         n climbs up until reaching a parent that has a right child
        //         (which is not n), then return this right child
        while (n.parent != null && (n.parent.right == null || n.parent.right == n)) {
            n = n.parent;
        }
        // case 3: n is the last node in traversal ->
        //         return root's parent, ie., null
        if (n.parent == null) return null;
        return n.parent.right;
    }