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.

Practice

1. What is the inorder successor of a node in a Binary Search Tree (BST)?

easy

A. The node with the smallest key greater than the given node's key

B. The node with the largest key smaller than the given node's key

C. The left child of the given node

D. The right child of the given node

Solution

1. Step 1: Understand inorder traversal order

   Inorder traversal visits nodes in ascending order of their keys in a BST.

2. Step 2: Define inorder successor

   The inorder successor of a node is the next node visited after it in inorder traversal, which is the smallest node with a key greater than the current node.

3. Final Answer:

   The node with the smallest key greater than the given node's key -> Option A

4. Quick Check:

   Inorder successor = smallest greater key [OK]

Hint: Inorder successor is next bigger node in sorted order [OK]

Common Mistakes:

• Confusing successor with predecessor
• Thinking successor is always right child
• Assuming successor is parent node

2. Which of the following C++ function signatures correctly represents a function to find the inorder successor of a BST node given the root and the node? Assume Node is a struct with int key, and left/right pointers.

easy

A. Node inorderSuccessor(Node root, Node p);

B. int inorderSuccessor(Node root, int p);

C. void inorderSuccessor(Node* root, Node* p);

D. Node* inorderSuccessor(Node* root, Node* p);

Solution

1. Step 1: Analyze parameter types

   The function needs access to the BST root and the target node pointer, so pointers are required.

2. Step 2: Analyze return type

   The function should return a pointer to the successor node or nullptr if none exists.

3. Final Answer:

   Node* inorderSuccessor(Node* root, Node* p); -> Option D

4. Quick Check:

   Use pointers for tree nodes and return pointer [OK]

Hint: Use pointers for tree nodes and return pointer [OK]

Common Mistakes:

• Passing nodes by value instead of pointer
• Returning void instead of Node*
• Using int instead of Node* for node parameters

3. Given the BST below and the node with key 15, what is the inorder successor's key?

        20
       /  \
     10    30
       \     \
       15    40

medium

A. 10

B. 20

C. 30

D. 40

Solution

1. Step 1: Locate node 15 and find successor

   Node 15 has no right child, so successor is the lowest ancestor whose left child is also ancestor of 15.

2. Step 2: Identify successor in BST

   20 is the parent of 15's ancestor and 15 is in left subtree of 20, so successor is 20.

3. Final Answer:

   20 -> Option B

4. Quick Check:

   Successor of 15 is 20 [OK]

Hint: If no right child, go up to first bigger ancestor [OK]

Common Mistakes:

• Choosing right child 30 incorrectly
• Choosing 40 which is too far
• Choosing 10 which is smaller

4. Consider this buggy C++ code snippet to find the inorder successor of a node in BST:

Node* inorderSuccessor(Node* root, Node* p) {
    if (p->right != nullptr) {
        Node* curr = p->right;
        while (curr->left != nullptr) {
            curr = curr->left;
        }
        return curr;
    }
    Node* succ = nullptr;
    while (root != nullptr) {
        if (p->key < root->key) {
            succ = root;
            root = root->left;
        } else {
            root = root->right;
        }
    }
    return succ;
}

What is the bug in this code?

medium

A. It does not check if p has a left child

B. It incorrectly updates succ when p->key == root->key

C. It does not handle the case when p is nullptr

D. It returns the wrong node when p has a right child

Solution

1. Step 1: Check null pointer dereference

   The code immediately accesses p->right and later p->key without verifying if p is nullptr, leading to a segmentation fault.

2. Step 2: Verify other logic

   Right subtree min is correctly found. Ancestor search properly sets succ only on left branches and handles equality by traversing right (null since no right child).

3. Final Answer:

   It does not handle the case when p is nullptr -> Option C

4. Quick Check:

   Missing p == nullptr check before dereference [OK]

Hint: Missing nullptr check for input node p [OK]

Common Mistakes:

• Ignoring nullptr checks for p
• Confusing left child check for successor
• Assuming bug in right subtree handling

5. You have a BST with nodes having keys: 5, 3, 7, 2, 4, 6, 8. You want to find the inorder successor of node with key 7. Which of the following is the correct approach to find it efficiently?

hard

A. If node 7 has right child, successor is leftmost node in right subtree; else, go up to first ancestor larger than 7

B. Successor is always the right child of node 7

C. Successor is the parent of node 7 regardless of children

D. Successor is the left child of node 7

Solution

1. Step 1: Check if node 7 has right child

   Node 7 has right child 8, so successor is leftmost node in right subtree, which is 8 itself.

2. Step 2: If no right child, find first ancestor larger than node

   This step is for cases where right child is absent, not applicable here.

3. Final Answer:

   If node 7 has right child, successor is leftmost node in right subtree; else, go up to first ancestor larger than 7 -> Option A

4. Quick Check:

   Right child exists, successor = leftmost right subtree [OK]

Hint: Check right subtree first; else climb ancestors [OK]

Common Mistakes:

• Assuming successor is always right child
• Ignoring ancestor climbing when no right child
• Confusing successor with parent node