Find the Inorder Successor in a Binary Search Tree

Algorithm Steps

Given a binary search tree (BST) and a target node p.
If p.right exists, the inorder successor is the leftmost node in the right subtree.
If p.right does not exist, initialize successor = null and traverse the tree starting from the root:
While traversing, if p.val < current.val, update successor to the current node and move to current.left; otherwise, move to current.right.
After the traversal, the recorded successor is the inorder successor of p.

Find the Inorder Successor in a Binary Search Tree - Code Examples Code

Python

Java

JavaScript

C++

Kotlin

Swift

Php

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def inorderSuccessor(root, p):
    if p.right:
        curr = p.right
        while curr.left:
            curr = curr.left
        return curr
    successor = None
    while root:
        if p.val < root.val:
            successor = root
            root = root.left
        else:
            root = root.right
    return successor

# Example usage:
if __name__ == '__main__':
    # Construct BST:
    #         5
    #        / \
    #       3   7
    #      / \   \
    #     2   4   8
    root = TreeNode(5, TreeNode(3, TreeNode(2), TreeNode(4)), TreeNode(7, None, TreeNode(8)))
    p = root.left  # Node with value 3
    successor = inorderSuccessor(root, p)
    print(successor.val if successor else None)