BST Find Maximum Element in DSA C++ - Build from Scratch

BST Find Maximum Element

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers. You want to find the largest number in this tree. This is like looking for the tallest person in a group by checking each person carefully.

🎯 Goal: Build a simple BST with given numbers, then write code to find and print the maximum element in the BST.

📋 What You'll Learn

Create a BST node structure with integer data and left/right pointers

Insert given numbers into the BST in the given order

Write a function to find the maximum element in the BST

Print the maximum element found

💡 Why This Matters

🌍 Real World

BSTs are used in databases and file systems to quickly find the largest or smallest values, like finding the newest or oldest record.

💼 Career

Understanding BST operations is important for software engineers working with data storage, search algorithms, and optimization.

1

Create BST Node Structure and Insert Nodes

Create a struct called Node with an int data, and two pointers left and right to Node. Then create a function insertNode that takes a Node* and an int value, and inserts the value into the BST following BST rules. Finally, create a Node* called root and insert these values in order: 15, 10, 20, 8, 12, 17, 25.

DSA C++

// Define struct Node
// Define insertNode function
// Create root and insert values 15, 10, 20, 8, 12, 17, 25
// Your code here

Hint

Remember, a BST node has data and pointers to left and right child nodes. Insert smaller values to the left, larger to the right.

2

Create a Function to Find Maximum Element

Create a function called findMax that takes a Node* called root and returns the maximum integer value in the BST. Use the property that the maximum value is found by going as far right as possible.

DSA C++

#include 
using namespace std;

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

Node* insertNode(Node* root, int value) {
    if (root == nullptr) {
        Node* newNode = new Node;
        newNode->data = value;
        newNode->left = nullptr;
        newNode->right = nullptr;
        return newNode;
    }
    if (value data) {
        root->left = insertNode(root->left, value);
    } else {
        root->right = insertNode(root->right, value);
    }
    return root;
}

int findMax(Node* root) {
    // Your code here
}

int main() {
    Node* root = nullptr;
    root = insertNode(root, 15);
    root = insertNode(root, 10);
    root = insertNode(root, 20);
    root = insertNode(root, 8);
    root = insertNode(root, 12);
    root = insertNode(root, 17);
    root = insertNode(root, 25);

    // Your code here

    return 0;
}

Hint

Start from the root and keep moving to the right child until there is no right child left. The last node you reach has the maximum value.

3

Call findMax and Store Result

In the main function, call findMax with root and store the result in an int variable called maxValue.

DSA C++

#include 
using namespace std;

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

Node* insertNode(Node* root, int value) {
    if (root == nullptr) {
        Node* newNode = new Node;
        newNode->data = value;
        newNode->left = nullptr;
        newNode->right = nullptr;
        return newNode;
    }
    if (value data) {
        root->left = insertNode(root->left, value);
    } else {
        root->right = insertNode(root->right, value);
    }
    return root;
}

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

int main() {
    Node* root = nullptr;
    root = insertNode(root, 15);
    root = insertNode(root, 10);
    root = insertNode(root, 20);
    root = insertNode(root, 8);
    root = insertNode(root, 12);
    root = insertNode(root, 17);
    root = insertNode(root, 25);

    // Store the maximum value in maxValue
    // Your code here

    return 0;
}

Hint

Call findMax(root) and save the result in maxValue.

4

Print the Maximum Element

Print the value stored in maxValue using cout with the exact text: Maximum element in BST: followed by the value.

DSA C++

#include 
using namespace std;

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

Node* insertNode(Node* root, int value) {
    if (root == nullptr) {
        Node* newNode = new Node;
        newNode->data = value;
        newNode->left = nullptr;
        newNode->right = nullptr;
        return newNode;
    }
    if (value data) {
        root->left = insertNode(root->left, value);
    } else {
        root->right = insertNode(root->right, value);
    }
    return root;
}

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

int main() {
    Node* root = nullptr;
    root = insertNode(root, 15);
    root = insertNode(root, 10);
    root = insertNode(root, 20);
    root = insertNode(root, 8);
    root = insertNode(root, 12);
    root = insertNode(root, 17);
    root = insertNode(root, 25);

    int maxValue = findMax(root);

    // Print the maximum element
    // Your code here

    return 0;
}

Hint

Use cout to print the text and the maxValue variable on the same line.

Practice

1. In a Binary Search Tree (BST), where is the maximum element always located?

easy

A. At the leftmost node

B. At any leaf node

C. At the root node

D. At the rightmost node

Solution

1. Step 1: Understand BST property

   In a BST, left child nodes have smaller values and right child nodes have larger values than their parent.

2. Step 2: Locate maximum element

   The maximum element is the rightmost node because it has no right child and is greater than all other nodes.

3. Final Answer:

   At the rightmost node -> Option D

4. Quick Check:

   Maximum = rightmost node [OK]

Hint: Maximum is always the rightmost node in BST [OK]

Common Mistakes:

• Confusing maximum with root node
• Thinking maximum is at leftmost node
• Assuming maximum can be any leaf

2. Which of the following C++ function signatures correctly finds the maximum element in a BST node pointer root?

easy

A. int findMax(Node* root) { return root->data; }

B. int findMax(Node* root) { while(root->left) root = root->left; return root->data; }

C. int findMax(Node* root) { while(root->right) root = root->right; return root->data; }

D. int findMax(Node* root) { while(root->parent) root = root->parent; return root->data; }

Solution

1. Step 1: Check traversal direction for maximum

   Maximum is found by moving right until no right child exists.

2. Step 2: Verify code correctness

   int findMax(Node* root) { while(root->right) root = root->right; return root->data; } correctly loops while root->right exists and returns root->data.

3. Final Answer:

   int findMax(Node* root) { while(root->right) root = root->right; return root->data; } -> Option C

4. Quick Check:

   Traverse right child to find max [OK]

Hint: Traverse right child pointer until null [OK]

Common Mistakes:

• Traversing left child instead of right
• Returning root data without traversal
• Using parent pointer which may not exist

3. What will be the output of the following C++ code snippet?

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

Node* root = new Node{10, nullptr, nullptr};
root->right = new Node{20, nullptr, nullptr};
root->right->right = new Node{30, nullptr, nullptr};

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

std::cout << findMax(root) << std::endl;

medium

A. 30

B. 20

C. 10

D. Runtime error

Solution

1. Step 1: Trace the BST structure

   Root is 10, right child 20, right child's right child 30.

2. Step 2: Follow findMax function

   Loop moves from 10 to 20, then 20 to 30, then stops as 30 has no right child.

3. Final Answer:

   30 -> Option A

4. Quick Check:

   Rightmost node data = 30 [OK]

Hint: Rightmost node data is maximum [OK]

Common Mistakes:

• Returning root data without traversal
• Confusing left and right pointers
• Assuming runtime error due to nullptr

4. Identify the bug in the following C++ function to find the maximum element in a BST:

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

medium

A. Should traverse right child, not left child

B. Should return 0 instead of -1 for nullptr

C. Missing check for root->right in while loop

D. Function should be void, not int

Solution

1. Step 1: Analyze traversal direction

   The function incorrectly traverses left child to find maximum, but maximum is at rightmost node.

2. Step 2: Correct traversal logic

   Change while(root->left) to while(root->right) to find maximum correctly.

3. Final Answer:

   Should traverse right child, not left child -> Option A

4. Quick Check:

   Maximum = rightmost node, not leftmost [OK]

Hint: Maximum is rightmost, so traverse right pointer [OK]

Common Mistakes:

• Traversing left child instead of right
• Ignoring nullptr check
• Returning wrong default value

5. Given a BST where some nodes have duplicate values, which approach correctly finds the maximum element considering duplicates are allowed on the right subtree?

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

// Function to find max element
int findMax(Node* root) {
  // Your code here
}

hard

A. Traverse right while root->right exists and root->right->data > root->data

B. Traverse right while root->right exists only

C. Traverse left while root->left exists and root->left->data > root->data

D. Return root->data without traversal

Solution

1. Step 1: Understand duplicates in BST

   Even with duplicates allowed on the right subtree, BST property ensures right subtree values are >= parent, so maximum is always the rightmost node.

2. Step 2: Correct traversal for maximum

   Traverse right while root->right exists only. No data comparison needed due to BST invariants.

3. Final Answer:

   Traverse right while root->right exists only -> Option B

4. Quick Check:

   Traverse right child pointer until null [OK]

Hint: Traverse right child pointer until null [OK]

Common Mistakes:

• Using strict > check which stops early on duplicates
• Traversing left instead of right
• Returning root data without traversal