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

1. 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

1. 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`:

1. If `N` has a right child:
   • Set `N` to `N.right`
   • While `N.left` is not null:
     • Set `N` to `N.left`
   • Return `N`
2. 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.