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

Binary Search Trees

Contents

ProblemExamplesSolutionAlgorithmCode

Problem Statement❯

Given a binary search tree (BST) and a node p in it, find the inorder successor of that node. The inorder successor of a node is the node with the smallest key greater than p.val.

Note: It is guaranteed that the given node p exists in the tree. However, the successor might or might not exist.

Examples❯

Input Tree Target Node (p) Inorder Successor Description
[20, 10, 30, 5, 15, 25, 35]
15 20 Inorder successor of 15 is 20, the lowest ancestor for which 15 is in left subtree.
[20, 10, 30, 5, 15, 25, 35]
10 15 Successor is leftmost node in 10's right subtree: 15.
[20, 10, 30, 5, 15, 25, 35]
30 35 30 has a right child, and its leftmost node is 35 — the inorder successor.
[20, 10, 30, 5, 15, 25, 35]
35 null 35 is the rightmost node; it has no inorder successor.
[20, 10, null, 5, 15]
5 10 5 has no right child. Successor is the lowest ancestor for which 5 lies in the left subtree — 10.
[8, 3, 10, 1, 6, null, 14, null, null, 4, 7, 13]
6 7 6 has right child 7 → it's the inorder successor.

Solution❯

Understanding the Problem

We are given a Binary Search Tree (BST) and a node p. Our goal is to find the inorder successor of this node. An inorder successor is the node that comes immediately after p in the inorder traversal of the tree.

In an inorder traversal of a BST, we visit nodes in ascending order: left subtree → current node → right subtree. So, the inorder successor of a node p is the node with the smallest key greater than p.val.

Step-by-Step Solution with Example

step 1: Identify if node p has a right child

If p has a right child, then its inorder successor will be the leftmost node in the right subtree. This is because we go right once, and then as left as possible to find the next smallest value.

Example: Consider a BST: [4, 2, 6, null, 3, 5, 7]. If p = 4, since 4 has a right child (6), we go to 6, and then go left to find 5. So, the inorder successor is 5.

step 2: Handle the case when node p has no right child

If p does not have a right child, then we have to look at its ancestors. Specifically, we look for the lowest ancestor for which p is in its left subtree. This ancestor will be the next node in the inorder traversal.

We start from the root and simulate the traversal path to p. During this path, if we ever move left, we store the current node as a potential successor. If we move right, we do not update the successor.

Example: For the same BST, if p = 5, it has no right child. Starting from root (4), we move right to 6, then left to 5. Since we moved left from 6 to 5, 6 becomes the successor.

step 3: Account for edge case where p is the largest node

If p is the largest node in the tree, it will not have a successor. There is no node with a value greater than p, so the result should be null.

Example: If p = 7 in the same BST, 7 is the largest. There is no node after 7 in inorder traversal, so the answer is null.

step 4: Traverse and return the stored successor

We either return the leftmost node in the right subtree (step 1), or the stored ancestor (step 2). If neither exists, we return null.

Edge Cases

Tree is empty

If the BST is empty, there are no nodes to process. Return null.

Node p is null

If the input node is null, there’s no way to find a successor. Return null.

Tree has only one node

If the tree contains just one node and that node is p, there is no successor to find. Return null.

Node p is not present in the tree

This depends on the implementation — either you check if p exists in the tree or you assume it does. If it doesn’t exist, the answer should be null or an error should be raised depending on requirements.

Finally

Finding the inorder successor in a BST is an important operation and relies on understanding tree traversal and BST properties. By breaking the problem into two main scenarios (right child exists vs. no right child), and walking through intuitive examples, we can confidently solve this problem. Always remember to include boundary conditions like null nodes or the largest element to make your solution robust.

Algorithm Steps❯

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

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left, *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

TreeNode* inorderSuccessor(TreeNode* root, TreeNode* p) {
    if (p->right) {
        TreeNode* curr = p->right;
        while (curr->left) curr = curr->left;
        return curr;
    }
    TreeNode* successor = NULL;
    while (root) {
        if (p->val < root->val) {
            successor = root;
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return successor;
}

int main() {
    TreeNode* root = createNode(5);
    root->left = createNode(3);
    root->right = createNode(7);
    root->left->left = createNode(2);
    root->left->right = createNode(4);
    root->right->right = createNode(8);
    TreeNode* p = root->left; // Node with value 3
    TreeNode* succ = inorderSuccessor(root, p);
    printf("%d\n", succ ? succ->val : -1);
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...