In Order Successor in Binary Search Tree
Master System Design with Codemia
Enhance your system design skills with over 120 practice problems, detailed solutions, and hands-on exercises.
Understanding In-Order Successor in Binary Search Tree
In the context of a Binary Search Tree (BST), the in-order successor of a node is the node that would appear immediately after the given node in an in-order traversal. This essential operation is vital for several tasks, such as deletion or in scenarios where nodes need to be processed in sorted order.
Definition of In-Order Successor
For a given node `N` in a BST, its in-order successor is the node with the smallest key greater than `N`'s key. The in-order successor is a vital concept used in BST operations like deletion, where rearrangement of nodes preserving the BST properties is required.
How to Find the In-Order Successor
The process of finding the in-order successor depends on the structure of the BST and the position of the current node within this structure. Here's a detailed breakdown of the procedure:
Case 1: Node with a Right Child
- If node `N` has a right child, the successor is the leftmost node in `N`'s right subtree. This is because all nodes in the right subtree of `N` are greater than `N`, and finding the minimum in this subtree gives the next greater element.
Case 2: Node without a Right Child
- If node `N` does not have a right child, then the successor is one of the ancestors. You need to travel up the tree until you find a node that is the left child of its parent. The parent of this node is the in-order successor.
Here is a step-by-step algorithm for finding the in-order successor of the node `N`:
- If `N` has a right child:
- Set `N` to `N.right`
- While `N.left` is not null:
- Set `N` to `N.left`
- Return `N`
- If `N` has no right child:
- Let `current` point to `N`
- While `current.parent` is not null and `current` is the right child of `current.parent`:
- Set `current` to `current.parent`
- Return `current.parent`
Example
Consider the following BST:
5 15 25 35
- In-Order Successor of 10: It is `12` since `12` is the minimum node in the right subtree of `10`.
- In-Order Successor of 15: It is `17` because `17` is the minimum node in the right subtree of `15`.
- In-Order Successor of 30: It is `35` as `30` is the parent of `35`, and `35` has no left child.

