On this page
Description
A key's neighbors in sorted order are its predecessor, the largest value below it, and its successor, the smallest value above it. Listing every value in order finds them in O(n). A BST does better. Both neighbors lie on the path a search for the key takes, so one walk down from the root finds them. That holds even when the key isn't in the tree.
We'll go from simple to more technical:
- The pattern: one walk that records a candidate on each side.
- A second flavor: the successor of a node with only parent pointers.
- Where neighbors are asked for in production (calendars, order books, sorted maps).
- What breaks it: absent keys, "the parent is the successor", and sentinel values.
The approach
Walk down as if searching for the key. A node smaller than the key is a predecessor candidate, and you step right. A node larger than the key is a successor candidate, and you step left. Each new candidate replaces the old one on its side.
Here is the walk for 65, which isn't in the tree [50, 30, 70, 20, 40, 60, 80]:
| At | Compared with 65 | Step | pred | succ |
|---|---|---|---|---|
| 50 | smaller | right | 50 | none |
| 70 | larger | left | 50 | 70 |
| 60 | smaller | right | 60 | 70 |
| (null) | - | stop | 60 | 70 |
If the walk finds the key itself, its own subtrees hold anything closer. The predecessor is then the largest value in its left subtree, and the successor is the smallest in its right subtree.
Java
int[] findPreSuc(TreeNode root, int key) {
int pred = -1, succ = -1; // -1 = "none" (values here are non-negative)
TreeNode cur = root;
while (cur != null) {
if (cur.val == key) {
if (cur.left != null) { // predecessor: rightmost node of the left subtree
TreeNode t = cur.left;
while (t.right != null) t = t.right;
pred = t.val;
}
if (cur.right != null) { // successor: leftmost node of the right subtree
TreeNode t = cur.right;
while (t.left != null) t = t.left;
succ = t.val;
}
break;
} else if (key < cur.val) {
succ = cur.val; // larger than key - a successor candidate
cur = cur.left;
} else {
pred = cur.val; // smaller than key - a predecessor candidate
cur = cur.right;
}
}
return new int[]{pred, succ};
}
Python
def find_pre_suc(root: TreeNode | None, key: int) -> list[int]:
pred = succ = -1 # -1 = "none" (values here are non-negative)
cur = root
while cur is not None:
if cur.val == key:
if cur.left is not None: # predecessor: rightmost node of the left subtree
t = cur.left
while t.right is not None:
t = t.right
pred = t.val
if cur.right is not None: # successor: leftmost node of the right subtree
t = cur.right
while t.left is not None:
t = t.left
succ = t.val
break
elif key < cur.val:
succ = cur.val # larger than key - a successor candidate
cur = cur.left
else:
pred = cur.val # smaller than key - a predecessor candidate
cur = cur.right
return [pred, succ]
Why is replacing a candidate safe? After stepping left from a node A, every node ahead is in A's left subtree, so it's smaller than A. Any later successor candidate sits between the key and A, which is tighter. Right steps work the same way for predecessors. The walk is O(h).
A second flavor: successor without the root
Sometimes you get a node, not a key, and each node has a parent pointer. The same two cases apply:
Java
TreeNode inorderSuccessor(TreeNode node) {
if (node.right != null) { // case 1: leftmost node of the right subtree
TreeNode cur = node.right;
while (cur.left != null) cur = cur.left;
return cur;
}
TreeNode cur = node; // case 2: climb while we're a right child
while (cur.parent != null && cur == cur.parent.right) cur = cur.parent;
return cur.parent; // first ancestor reached from its left side (or null)
}
Python
def inorder_successor(node: TreeNode) -> TreeNode | None:
if node.right is not None: # case 1: leftmost node of the right subtree
cur = node.right
while cur.left is not None:
cur = cur.left
return cur
cur = node # case 2: climb while we're a right child
while cur.parent is not None and cur is cur.parent.right:
cur = cur.parent
return cur.parent # first ancestor reached from its left side (or None)
Climbing up from a right child reaches a smaller ancestor, whose turn in sorted order is already over. The first ancestor you reach from its left side comes next. If you climb past the root, the node was the largest value.
Where you'll see it
Nearest neighbors in sorted data: the bookings around a time, the price levels around a target in an order book, the next key after a cursor. Java's TreeMap.lowerKey and higherKey are exactly these two.
Which tool for which job?
| You need | Use |
|---|---|
| Both neighbors of a key, present or not | one walk: a right step records a predecessor, a left step a successor |
| The next node from a node, no root | parent pointers: the right subtree's minimum, or climb until you come up from a left child |
| Neighbors in Java | TreeMap.lowerKey / higherKey (floorKey / ceilingKey include the key) |
| Neighbors in Python | bisect on a sorted list |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| Handling only keys in the tree | an absent key gets no answer | the candidate walk handles it with no extra code |
| Returning the parent as the successor | wrong when the node is a right child | climb until you arrive from a left child |
| -1 as "none" when -1 is a real value | a real neighbor and "none" look the same | return null / None |
int next = map.higherKey(k) on the largest key | NullPointerException on unboxing | keep it an Integer and check for null |
| Listing everything in order to find two neighbors | O(n) instead of O(h) | one walk down |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. In [50, 30, 70, 20, 40, 60, 80], what are the predecessor and successor of 25 (not in the tree)?
Show answer
20 and 30. The walk goes left at 50 and left at 30, so the successor candidate becomes 30. Then it goes right at 20, so the predecessor is 20, and it falls off.
2. Node 40 in the same tree has no right child. What is its successor, and why isn't it its parent?
Show answer
- 40 is the right child of 30, so 30 is smaller and comes first. Climbing from 30 to 50 arrives from the left side, so 50 comes next.
3. Why does overwriting succ on every left step never throw away a better answer?
Show answer
After a left step from A, everything still reachable is smaller than A. So a later successor candidate lies between the key and A, which is tighter on that side.
Key takeaways
- Both neighbors of a key are on its search path - one O(h) walk finds them, key present or not.
- A right step records a predecessor candidate, a left step a successor candidate.
- An exact match adds the left subtree's maximum and the right subtree's minimum.
- Without the root, climb until you arrive from a left child.