in-order successor
The node with the next larger key in a binary search tree, which is the smallest key in the node's right subtree.
In more detail
Deleting a node with two children copies its in-order successor's key into it and then deletes the successor, which has at most one child. That reduces the hard case to one of the two easy ones: removing a leaf, or splicing out a node with one child.
Related terms
- binary search tree — A binary tree in which every key in a node's left subtree is smaller than the node's key and every key in its right subtree is larger.
- in-order traversal — Visiting a binary tree's left subtree, then the node itself, then its right subtree.
Taught in
- Binary Search Trees: Search, Insert And Delete — Algorithms & Data Structures for Working Engineers
- Depth-First Search, Cycles And Topological Order — Algorithms & Data Structures for Working Engineers