BST Inorder Successor in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find the inorder successor of a node in BST

What is the output of the following C++ code that finds the inorder successor of a node with value 15 in the BST?

DSA C++

#include <iostream>

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

Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left != nullptr) {
        current = current->left;
    }
    return current;
}

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

int main() {
    Node* root = new Node(20);
    root->left = new Node(10);
    root->right = new Node(30);
    root->left->left = new Node(5);
    root->left->right = new Node(15);
    Node* p = root->left->right; // Node with value 15
    Node* succ = inorderSuccessor(root, p);
    if (succ != nullptr) {
        std::cout << succ->val << std::endl;
    } else {
        std::cout << "null" << std::endl;
    }
    return 0;
}

A 15

B 20

C null

D 30

💡 Hint

Remember inorder successor is the smallest node greater than the given node.

The inorder successor of 15 is 20 because 15 has no right child, so we look up to ancestors. 20 is the next bigger node after 15 in inorder traversal.

❓ Predict Output

intermediate

Inorder successor when node has right subtree

What will be printed by this C++ code when finding the inorder successor of node with value 10?

DSA C++

#include <iostream>

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

Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left != nullptr) {
        current = current->left;
    }
    return current;
}

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

int main() {
    Node* root = new Node(20);
    root->left = new Node(10);
    root->right = new Node(30);
    root->left->left = new Node(5);
    root->left->right = new Node(15);
    Node* p = root->left; // Node with value 10
    Node* succ = inorderSuccessor(root, p);
    if (succ != nullptr) {
        std::cout << succ->val << std::endl;
    } else {
        std::cout << "null" << std::endl;
    }
    return 0;
}

A 5

B null

C 20

D 15

💡 Hint

If the node has a right child, the successor is the leftmost node in that right subtree.

Node 10 has a right child 15. The inorder successor is the smallest node in the right subtree, which is 15.

🔧 Debug

advanced

Identify the error in inorder successor code

What error will this code produce when trying to find the inorder successor of node with value 25?

DSA C++

#include <iostream>

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

Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left != nullptr) {
        current = current->left;
    }
    return current;
}

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

int main() {
    Node* root = new Node(20);
    root->left = new Node(10);
    root->right = new Node(30);
    root->right->left = new Node(25);
    root->right->right = new Node(35);
    Node* p = root->right->left; // Node with value 25
    Node* succ = inorderSuccessor(root, p);
    if (succ != nullptr) {
        std::cout << succ->val << std::endl;
    } else {
        std::cout << "null" << std::endl;
    }
    return 0;
}

A null

B 20

C 30

D Segmentation fault

💡 Hint

Check if the node has a right child and what the successor should be.

Node 25 has no right child. The successor is the lowest ancestor whose left child is also ancestor of 25, which is 30.

❓ Predict Output

advanced

Inorder successor for the maximum node in BST

What will this code print when finding the inorder successor of the node with value 35 (maximum node)?

DSA C++

#include <iostream>

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

Node* minValueNode(Node* node) {
    Node* current = node;
    while (current && current->left != nullptr) {
        current = current->left;
    }
    return current;
}

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

int main() {
    Node* root = new Node(20);
    root->left = new Node(10);
    root->right = new Node(30);
    root->right->left = new Node(25);
    root->right->right = new Node(35);
    Node* p = root->right->right; // Node with value 35
    Node* succ = inorderSuccessor(root, p);
    if (succ != nullptr) {
        std::cout << succ->val << std::endl;
    } else {
        std::cout << "null" << std::endl;
    }
    return 0;
}

A null

B 35

C 30

D 25

💡 Hint

The maximum node has no inorder successor in BST.

Node 35 is the largest node and has no right child. No ancestor is greater than 35, so successor is null.

🧠 Conceptual

expert

Inorder successor concept in BST with parent pointers

Given a BST where each node has a parent pointer, which of the following is the correct approach to find the inorder successor of a node p?

A If p has right child, successor is leftmost node in right subtree; else move up using parent pointers until a node is left child of its parent, then return that parent.

B If p has left child, successor is rightmost node in left subtree; else move up using parent pointers until a node is right child of its parent, then return that parent.

C Successor is always the parent node regardless of children.

D If p has no children, successor is the root of the BST.

💡 Hint

Think about inorder traversal order and how parent pointers help.

Inorder successor is next node in inorder traversal. If right child exists, successor is leftmost node in right subtree. Otherwise, move up until you find a node that is left child of its parent; that parent is successor.