BST Predecessor vs Successor: Two Valid Ways to Replace a Deleted Node

Introduction

When a node has two children, its replacement cannot be an arbitrary value. It must be a nearby value that keeps the rule of the binary search tree correct: smaller values remain on the left and larger values remain on the right.

For example, if the target is 20, a suitable replacement can come from just below it in sorted order or just above it. The two choices are called the predecessor and the successor.

The replacement question

When a binary search tree node has two children, deletion needs a value that can safely occupy its position. The previous article covered the three deletion cases; this article focuses on the choice inside the two-child case.

There are two natural candidates:

• The inorder predecessor is the largest value in the node's left subtree.
• The inorder successor is the smallest value in the node's right subtree.

Both sit immediately next to the deleted value when the tree is read in sorted order. This is why either one can preserve the BST ordering rule. An arbitrary descendant does not necessarily have the correct position in that order.

The word inorder refers to visiting a node's left subtree, then the node itself, and then its right subtree. For a valid BST, this produces the values in sorted order. Therefore, the predecessor is the value immediately before the target, and the successor is the value immediately after it.

Finding each candidate

Use the target value 20 in the example tree:

        20
       /  \
     10    30
       \   /  \
       15 25  40

To find its predecessor, move left once to 10, then move right as far as possible. The rightmost value in that subtree is 15.

To find its successor, move right once to 30, then move left as far as possible. The leftmost value in that subtree is 25.

The directions are mirror images:

If the relevant subtree is absent, that candidate does not exist. A deletion implementation must therefore only enter this replacement logic when both child subtrees are present, or handle the missing side explicitly.

Why both preserve the invariant

Every value in the left subtree is lower than 20, and every value in the right subtree is higher. The predecessor 15 is the greatest value that is still lower than 20. Replacing 20 with 15 therefore keeps the values on its left lower and the values on its right higher. The successor 25 is the smallest value that is higher than 20, so the same reasoning works in the other direction.

This is the important reason for choosing one of these boundary values. The replacement is not chosen simply because it is a child or because it is nearby. It is chosen because its position in sorted order has been established.

The replacement is not complete after copying a value. The selected node still exists in its original subtree, so the algorithm must delete that original node. Fortunately, the predecessor has no right child and the successor has no left child; their follow-up deletion is simpler than the original two-child case.

What this repository chooses

In src/bst.js, the repository chooses the inorder successor. Its deletion branch starts at node.right, follows left links until the smallest right-subtree node is reached, recursively deletes that successor from node.right, and then assigns the successor's data to the target node.

That ordering is a repository fact, not a claim that successor replacement is universally better. The source keeps the replacement search inline inside its recursive deletion method, consistent with the project's implementation style.

The repository removes duplicate input values while building a tree, and insert ignores a value already present. With that policy, the candidate values are unique. A tree that permits duplicates would need a stated “equal values go left” or “equal values go right” rule and would apply it during both search and deletion.

A focused walkthrough

Starting from the example tree, deleting 20 with the repository's strategy follows this path:

1. Search comparisons reach node 20.
2. Because it has two children, enter its right subtree at 30.
3. Follow the left edge to 25; there is no further left child.
4. Delete the original 25 from under 30.
5. Store 25 in the node that previously stored 20.

The resulting tree has one 25, keeps 10 and 15 below it, and keeps 30 and 40 above it. The old successor position is repaired rather than left as a duplicate.

Comparing the choices

For a target with two children, predecessor and successor have the same asymptotic search cost: each follows one downward path, O(h) in a tree of height h. Their practical path lengths can differ because the left and right subtrees may have different shapes. That is a property of the particular tree, not a universal superiority claim.

The most important rule is consistency. Use a candidate whose boundary relationship is proven, then remove it from its old position using the same BST rules. The successor is not universally better than the predecessor; it is simply the choice made by this repository.

Invariant checks for either strategy

After replacement, verify:

• all values in every left subtree are lower under the project's numeric comparison;
• all values in every right subtree are higher;
• the replacement value appears exactly once;
• every node that should remain is reachable from the root; and
• the originally deleted value is absent.

An inorder traversal is a compact diagnostic: for this repository's no-duplicate policy, it should produce a strictly increasing sequence after deletion.

Reflection

Predecessor and successor initially looked like competing tricks. Thinking of them as the two nearest inorder neighbors made the choice predictable. The repository's successor walk is easy to trace because it follows one direction after entering the right subtree, while the important correctness step is the same for both choices: repair the candidate's original location.

For the complete deletion cases and recursive root updates, see Deleting a Node from a Binary Search Tree: The Three Cases.

Key takeaways

• Predecessor is the maximum of the left subtree; successor is the minimum of the right subtree.
• Either candidate preserves the BST ordering invariant because it is an inorder boundary value.
• This repository uses the successor: right once, then left repeatedly.
• Copying the replacement value must be followed by deleting the original candidate node.
• Neither strategy is universally better; tree shape determines the exact path length.

Sources

• Author repository: Binary-Search-Tree
• Tree implementation and deletion method
• The Odin Project: Binary Search Trees
• Introduction to Algorithms, binary-search-tree chapter