BST Inorder Successor in DSA C++

Mental Model

The inorder successor of a node in a BST is the next node in sorted order. It is the smallest node greater than the given node.

Analogy: Imagine a line of people sorted by height. The inorder successor is the person just taller than you in the line.

      5
     / \
    3   7
   / \   \
  2   4   8

Node: 4 ↑

Dry Run Walkthrough

Input: BST: 5 -> 3 -> 7 -> 2 -> 4 -> 8, find inorder successor of node 4

Goal: Find the node that comes right after 4 in sorted order

Step 1: Check if node 4 has right child

5 -> 3 -> 7 -> 2 -> 4 ↑ -> 8
No right child for 4

Why: If right child exists, successor is leftmost node in right subtree

Step 2: Since no right child, move up to parent nodes to find first ancestor greater than 4

Current node 4 ↑, parent 3, grandparent 5

Why: Successor is first ancestor where node is in left subtree

Step 3: 4 is right child of 3, move up to 5

Node 4 -> parent 3 -> grandparent 5 ↑

Why: Keep moving up until node is left child of ancestor

Step 4: 5 is greater than 4 and 4 is in left subtree of 5, so successor is 5

Successor found: 5

Why: This ancestor is the next bigger node after 4

Result:

Successor of 4 is 5

Annotated Code

DSA C++

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node* parent;
    Node(int x) : val(x), left(nullptr), right(nullptr), parent(nullptr) {}
};

Node* leftmost(Node* node) {
    while (node && node->left) {
        node = node->left; // go left to find smallest
    }
    return node;
}

Node* inorderSuccessor(Node* node) {
    if (!node) return nullptr;
    if (node->right) {
        return leftmost(node->right); // successor in right subtree
    }
    Node* p = node->parent;
    while (p && node == p->right) {
        node = p; // move up while node is right child
        p = p->parent;
    }
    return p; // first ancestor where node is left child
}

int main() {
    // Build tree
    Node* root = new Node(5);
    Node* n3 = new Node(3);
    Node* n7 = new Node(7);
    Node* n2 = new Node(2);
    Node* n4 = new Node(4);
    Node* n8 = new Node(8);

    root->left = n3; n3->parent = root;
    root->right = n7; n7->parent = root;
    n3->left = n2; n2->parent = n3;
    n3->right = n4; n4->parent = n3;
    n7->right = n8; n8->parent = n7;

    Node* succ = inorderSuccessor(n4);
    if (succ) cout << succ->val << "\n";
    else cout << "null\n";
    return 0;
}

if (node->right) { return leftmost(node->right); }

If right child exists, successor is leftmost node in right subtree

while (p && node == p->right) { node = p; p = p->parent; }

Move up until node is left child of ancestor

return p;

Return first ancestor greater than node

Output

5

Complexity Analysis

Time: O(h) because in worst case we move up or down the height of the tree

Space: O(1) because we use only a few pointers, no extra data structures

vs Alternative: Naive approach would do inorder traversal and store nodes, costing O(n) time and space; this method is efficient using BST properties

Edge Cases

Node has right subtree

Successor is leftmost node in right subtree

DSA C++

if (node->right) { return leftmost(node->right); }

Node is the maximum node (no successor)

Returns null because no bigger node exists

DSA C++

while (p && node == p->right) { node = p; p = p->parent; }

Node is null

Returns null safely

DSA C++

if (!node) return nullptr;

When to Use This Pattern

When asked for the next bigger element in a BST, use inorder successor logic by checking right subtree or climbing ancestors.

Common Mistakes

Mistake: Not checking if node has right child first and always climbing ancestors
Fix: Always check right subtree first to find successor quickly

Mistake: Stopping climb too early or not checking if node is left child
Fix: Continue climbing until node is left child of ancestor or root reached

Summary

Finds the next bigger node after a given node in a BST.

Use when you need the sorted next element in BST traversal or queries.

If right child exists, successor is leftmost in right subtree; else climb ancestors until node is left child.