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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Inorder Predecessor Function in BST

What is the output of the following C++ code that finds the inorder predecessor of a given node in a BST?

DSA C++

struct Node {
    int data;
    Node* left;
    Node* right;
};

Node* inorderPredecessor(Node* root, Node* p) {
    Node* predecessor = nullptr;
    while (root) {
        if (p->data <= root->data) {
            root = root->left;
        } else {
            predecessor = root;
            root = root->right;
        }
    }
    return predecessor;
}

int main() {
    Node n1{20, nullptr, nullptr};
    Node n2{10, nullptr, nullptr};
    Node n3{30, nullptr, nullptr};
    Node n4{5, nullptr, nullptr};
    Node n5{15, nullptr, nullptr};

    n1.left = &n2; n1.right = &n3;
    n2.left = &n4; n2.right = &n5;

    Node* pred = inorderPredecessor(&n1, &n5);
    if (pred) {
        std::cout << pred->data << std::endl;
    } else {
        std::cout << "No predecessor" << std::endl;
    }
    return 0;
}

A 20

B 15

C 10

D No predecessor

💡 Hint

Think about the largest value smaller than the node 15 in the BST.

The inorder predecessor of node 15 is the largest node smaller than 15. In this BST, 10 is the predecessor because it is less than 15 and the closest smaller value.

🧠 Conceptual

intermediate

Understanding Inorder Predecessor in BST

In a Binary Search Tree (BST), which of the following best describes the inorder predecessor of a node?

A The node with the largest value smaller than the given node's value

B The node with the smallest value larger than the given node's value

C The left child of the given node

D The right child of the given node

💡 Hint

Inorder traversal visits nodes in ascending order.

Inorder predecessor is the node that comes immediately before the given node in inorder traversal, which means it has the largest value smaller than the given node.

🔧 Debug

advanced

Identify the Error in Inorder Predecessor Code

What error does the following C++ code produce when trying to find the inorder predecessor of a node in a BST?

DSA C++

Node* inorderPredecessor(Node* root, Node* p) {
    if (!root) return nullptr;
    if (p->left) {
        Node* temp = p->left;
        while (temp->right) temp = temp->right;
        return temp;
    }
    Node* predecessor = nullptr;
    while (root) {
        if (p->data < root->data) {
            root = root->left;
        } else if (p->data > root->data) {
            predecessor = root;
            root = root->right;
        }
    }
    return predecessor;
}

// Called with p = nullptr

A No error, returns nullptr

B Compilation error due to missing return statement

C Infinite loop in while loop

D Segmentation fault due to dereferencing nullptr

💡 Hint

Check what happens if p is nullptr.

If p is nullptr, accessing p->left causes a segmentation fault because it dereferences a null pointer.

❓ Predict Output

advanced

Output of Inorder Predecessor for Root Node

What is the output of the following code when finding the inorder predecessor of the root node in a BST?

DSA C++

struct Node {
    int data;
    Node* left;
    Node* right;
};

Node* inorderPredecessor(Node* root, Node* p) {
    if (p->left) {
        Node* temp = p->left;
        while (temp->right) temp = temp->right;
        return temp;
    }
    Node* predecessor = nullptr;
    while (root) {
        if (p->data <= root->data) {
            root = root->left;
        } else {
            predecessor = root;
            root = root->right;
        }
    }
    return predecessor;
}

int main() {
    Node n1{20, nullptr, nullptr};
    Node n2{10, nullptr, nullptr};
    Node n3{30, nullptr, nullptr};
    n1.left = &n2; n1.right = &n3;

    Node* pred = inorderPredecessor(&n1, &n1);
    if (pred) {
        std::cout << pred->data << std::endl;
    } else {
        std::cout << "No predecessor" << std::endl;
    }
    return 0;
}

A 30

B 10

C No predecessor

D 20

💡 Hint

Check if root has a left subtree and find its rightmost node.

The root node 20 has a left child 10 with no right child, so the inorder predecessor is 10.

🚀 Application

expert

Number of Nodes with Inorder Predecessor in BST

Given a BST with nodes 5, 10, 15, 20, 25 inserted in that order, how many nodes have a valid inorder predecessor?

A 4

B 5

C 3

D 2

💡 Hint

The smallest node has no predecessor.

Inorder predecessor exists for all nodes except the smallest one. Here, 5 is smallest, so 4 nodes have predecessors.