BST Find Maximum Element in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find maximum element in a BST

What is the output of the following C++ code that finds the maximum element in a Binary Search Tree?

DSA C++

#include <iostream>

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

int findMax(Node* root) {
    if (!root) return -1;
    while (root->right) {
        root = root->right;
    }
    return root->data;
}

int main() {
    Node n1 = {10, nullptr, nullptr};
    Node n2 = {20, nullptr, nullptr};
    Node n3 = {5, nullptr, nullptr};
    n1.right = &n2;
    n1.left = &n3;
    int maxVal = findMax(&n1);
    std::cout << maxVal << std::endl;
    return 0;
}

A -1

B 20

C 10

D 5

💡 Hint

The maximum element in a BST is the rightmost node.

The function moves to the right child repeatedly until it reaches the rightmost node, which holds the maximum value 20.

❓ Predict Output

intermediate

Output when BST is empty

What will be the output of the following code when the BST root is nullptr?

DSA C++

#include <iostream>

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

int findMax(Node* root) {
    if (!root) return -1;
    while (root->right) {
        root = root->right;
    }
    return root->data;
}

int main() {
    Node* root = nullptr;
    int maxVal = findMax(root);
    std::cout << maxVal << std::endl;
    return 0;
}

A -1

B 0

C Segmentation fault

D Undefined behavior

💡 Hint

Check the base case for empty tree in the function.

The function returns -1 immediately if the root is nullptr, so output is -1.

🔧 Debug

advanced

Identify the error in maximum element finder

What error will the following code produce when trying to find the maximum element in a BST?

DSA C++

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

int findMax(Node* root) {
    while (root->right != nullptr) {
        root = root->left;
    }
    return root->data;
}

A Returns minimum element instead of maximum

B Segmentation fault due to null pointer dereference

C Returns maximum element correctly

D Compilation error due to missing return statement

💡 Hint

Check the direction of traversal inside the loop.

The code incorrectly moves left child inside the loop that checks for right child, so it returns minimum instead of maximum.

🧠 Conceptual

advanced

Maximum element in BST with duplicates

In a BST that allows duplicate values inserted to the right subtree, which node will the findMax function return?

A The root node always

B The leftmost node with the maximum value

C The rightmost node with the maximum value including duplicates

D The minimum value node

💡 Hint

Duplicates go to the right subtree, so maximum is the rightmost node.

Since duplicates are inserted to the right, the maximum value is at the rightmost node including duplicates.

🚀 Application

expert

Find maximum element after BST modification

Given a BST where a new node with value 25 is inserted as the right child of the node with value 20, what will be the output of findMax function?

DSA C++

#include <iostream>

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

int findMax(Node* root) {
    if (!root) return -1;
    while (root->right) {
        root = root->right;
    }
    return root->data;
}

int main() {
    Node n1 = {10, nullptr, nullptr};
    Node n2 = {20, nullptr, nullptr};
    Node n3 = {5, nullptr, nullptr};
    Node n4 = {25, nullptr, nullptr};
    n1.left = &n3;
    n1.right = &n2;
    n2.right = &n4;
    int maxVal = findMax(&n1);
    std::cout << maxVal << std::endl;
    return 0;
}

A 5

B 20

C 10

D 25

💡 Hint

The maximum is the rightmost node after insertion.

After inserting 25 as right child of 20, the rightmost node is 25, so findMax returns 25.