The in-order successor in a binary search tree problem

Before delving into this Answer, it would be helpful to look at an overview of binary search trees.

Problem statement

The in-order successor of a node in a binary search tree is the node with the smallest key greater than the key of the given node. In this problem, we must return this node when provided with a particular node in a tree. In this Answer, we’ll provide the algorithm and code to solve this problem and a quiz.

Algorithm

The algorithm for this code is as follows:

Initialize an empty node to return the result. This variable will store the in-order successor.
Begin at the root of the binary search tree.
Loop through the tree:
1. If the node value we need to find the successor of is greater than or equal to the current node’s value, move to the right subtree (no need to check the left subtree as the value is greater).
2. If the value is less than the current node’s value, update the result node to the current root node and move to the left subtree.
The result node will eventually hold the in-order successor. If the result remains None after the loop, there is no in-order successor in the binary search tree.

Code

The tree for this problem is illustrated below:

def inorder(root, p):
    result = None
    while root:
        if p.val >= root.val:
            root = root.right
        else:
            result = root
            root = root.left
    return result
root = Tree(10)
root.left = Tree(5)
root.right = Tree(20)
root.left.left = Tree(3)
root.left.right = Tree(8)
root.right.left = Tree(15)
root.right.right = Tree(25)
p = root.left.right
successor = inorder(root, p)
if successor:
    print(f"The inorder successor is", successor.val)
else:
    print(f"There is no inorder successor")

This code can be explained below:

Line 1: The definition of the inorder function, which takes the root and the node p as parameters.
Line 2: Define our node result, which we’ll return at the end of the function.
Line 4: Iterate through the tree provided in the parameter.
Lines 5–6: Check if the value of p should be located in the right subtree or the left subtree. If it’s the right subtree, adjust the value of root accordingly.
Lines 8–9: If the value is in the left subtree instead, we adjust the value of root. This will continue until the value of root becomes Null.
Line 11: The value returned by the function is the inorder successor. If its value is Null, it means that there’s no successor for the given value.
Lines 13–19: Populate our sample tree.
Lines 21–26: Code to call our function.

To try other examples by changing the inputs in the code above. Attempt the quiz below to test your concepts:

Free Resources

Learn in-demand tech skills in half the time

PRODUCTS

Mock Interview

New

Courses

Skill Paths

Projects

Assessments