Inorder Successor In Binary Search Tree

Inorder Successor in Binary Search Tree

The inorder successor in a binary search tree (BST) is the node that comes immediately after a given node when all nodes are visited in inorder traversal order: left subtree, root node, right subtree. Which means in a BST, inorder traversal visits nodes in ascending sorted order, so the inorder successor of a node is essentially the next larger value than that node’s value. Understanding the inorder successor is important because it helps with BST traversal, deletion, range queries, and many tree-based algorithms.

A binary search tree is a tree data structure where each node has at most two children. For every node, values in the left subtree are smaller than the node’s value, and values in the right subtree are greater than the node’s value. Because of this property, the inorder traversal of a BST produces values in sorted order. The inorder successor is therefore a key concept in working with ordered data stored in a BST.

What Is an Inorder Successor?

Given a node x in a binary search tree, the inorder successor is the node with the smallest key greater than x.key. If no such node exists, then x is the largest node in the tree, and it has no inorder successor Less friction, more output..

Take this: consider this BST:

        8
      /   \
     4     12
    / \   /  \
   2   6 10  14

The inorder traversal of this tree is:

2, 4, 6, 8, 10, 12, 14

From this sequence, we can see:

The inorder successor of 4 is 6
The inorder successor of 6 is 8
The inorder successor of 8 is 10
The inorder successor of 12 is 14
The inorder successor of 14 is None

The inorder successor is not necessarily the node’s right child. It depends on the structure of the tree That's the part that actually makes a difference..

Why Inorder Successor Matters in a BST

The inorder successor is useful because it allows efficient navigation through sorted data. In a BST, searching for a value takes O(h) time, where h is the height of the tree. The inorder successor can often be found in the same amount of time.

Some important uses of the inorder successor include:

Iterating through all nodes in sorted order
Deleting a node from a BST
Finding the next element after a given value
Implementing ordered sets and maps
Supporting range search operations
Building tree iterators without recursion

Take this: if you need to delete a node with two children, you often replace it with its inorder successor, which is the smallest node in its right subtree. This keeps the BST property valid.

Inorder Traversal Order

To understand the inorder successor, it is helpful to understand inorder traversal first.

Inorder traversal visits nodes in this order:

Traverse the left subtree
Visit the current node
Traverse the right subtree

This is often written as:

left → root → right

For a BST, this traversal gives values in non-decreasing sorted order Surprisingly effective..

Example:

The inorder traversal is:

1, 3, 4, 5, 8, 9

In this tree:

The successor of 3 is 4
The successor of 4 is 5
The successor of 5 is 8
The successor of 8 is 9
The successor of 9 is None

Cases for Finding the Inorder Successor

There are two main cases when finding the inorder successor of a node in a BST:

The node has a right subtree
The node does not have a right subtree

These cases determine whether the successor is found below the node or above it.

Case 1: Node Has a Right Subtree

If a node has a right subtree, then its inorder successor is the minimum value node in its right subtree.

This works because all values in the right subtree are greater than the current node. Among those values, the smallest one comes immediately after the current node in inorder order.

For example:

The inorder traversal is:

5, 10, 11, 12, 15, 20

The inorder successor of 10 is 11, because 11 is the minimum node in the right subtree of 10 Worth knowing..

To find it:

Move to the right child
Keep moving left until there is no left child
The final node is the inorder successor

Example:

Right child of 10 is 15
Move left to 12
Move left to 11
11 has no left child
So, 11 is the inorder successor

Python Example

def minValueNode(node):
    current = node
    while current.left:
        current = current.left
    return current

def inorder_successor_with_right_subtree(node):
    if node.right is None:
        return None
    return minValueNode(node.right)

Case 2: Node Does Not Have a Right Subtree

If a node does not have a right subtree, then its inorder successor must be one of its ancestors The details matter here..

This happens because, during inorder traversal, after finishing a node’s left subtree, the algorithm visits the node itself. If the node has no right subtree, the traversal immediately moves upward to find the first ancestor for which this node lies in its left subtree.

For example:

The inorder traversal is:

3, 5, 7, 10, 12, 15

The inorder successor of 7 is 10.

Node 7 has no right subtree, so we move upward:

7 is in the right subtree of 5, so 5 is not the successor
7 is in the left subtree of 10, so 10 is the successor

If a Parent Pointer Is Available

If each node has a parent pointer, the algorithm becomes simple.

def inorder_successor(node):
    if node is None:
        return None

    # Case 1: Node has a right subtree
    if node.right is not None:
        return minValueNode(node.right)

    # Case 2: Node has no right subtree
    parent = node.parent
    while parent is not None and node == parent.right:
        node = parent
        parent = parent.

    return parent

Inorder Successor In Binary Search Tree