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.