Successor

Write an algorithm to find the "next" node (i.e., in-order successor) of a given node in a binary search tree. You may assume that each node has a link to its parent.

For this you need to think about how an in-order traversal works and try to "reverse engineer" it.

Here's one step of the logic: The successor of a specific node is the leftmost node of the right subtree. What if there is no right subtree, though?

👉 Link here to the repo to solve the problem

👊 Solution 1

This is not the most difficult problem in the world, but we need to carefully think about the logic.

Recall that an in-order traversal traverses the left subtree, then the current node, then the right subtree.To approach this problem, we need to think very, very carefully about what happens.

Let's suppose we have a hypothetical node. We know that the order goes left subtree, then current side, then right subtree. So, the next node we visit should be on the right side.

But which node on the right subtree? It should be the first node we'd visit if we were doing an in-order traversal of that subtree.This means that it should be the leftmost node on the right subtree. Easy enough!

But what if the node doesn't have a right subtree? This is where it gets a bit trickier.

If a node n doesn't have a right subtree, then we are done traversing n's subtree. We need to pick up where we left off with n's parent, which we'll call q.

If n were to the right of q, then we have fully traversed q'ssubtree as well. We need to traverse upwards from q until we find a node x that we have not fully traversed. How do we know that we have not fully traversed a node x? We know we have hit this case when we move from a left node to its parent. The left node is fully traversed, but its parent is not.

what if we traverse all the way up the tree before finding a left child? This will happen only when we hit the very end of the in-order traversal. That is, if we're already on the far right of the tree, then there is no in-order successor. We should return null.

    public BinaryTreeNode getInOrderSuccessor(BinaryTreeNode n) {
        if (n == null) return null;
        
        // found the right children, return the leftmost node of the right subtree
        if (n.right != null) {
            return leftMostChild(n.right);
        } else {
            BinaryTreeNode q = n;
            BinaryTreeNode x = q.parent;
            // we want to go up until we are on the left instead of the right
            while (x != null && x.left != q) {
                q = x;
                x = x.parent;
            }
            return x;
        }
    }

    private BinaryTreeNode leftMostChild(BinaryTreeNode n) {
        if (n == null) return null;
        while (n.left != null) n = n.left;
        return n;
    }

---

Question borrowed from “Cracking the coding interview”