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 integer values. You want to find the largest value stored in this tree. This is useful in many real-world cases, such as finding the highest score in a game leaderboard or the maximum price in a product catalog.

🎯 Goal: Build a simple BST with given nodes, 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

Manually create a BST with these exact nodes: 15 (root), 10 (left child), 20 (right child), 8 (left child of 10), 12 (right child of 10), 17 (left child of 20), 25 (right child of 20)

Write a function to find the maximum element in the BST by traversing to the rightmost node

Print the maximum element found

💡 Why This Matters

🌍 Real World

Finding maximum values in sorted data structures like BSTs is common in databases, search engines, and real-time analytics to quickly get highest scores, prices, or priorities.

💼 Career

Understanding BSTs and how to traverse them is fundamental for software engineers working with data storage, retrieval, and optimization algorithms.

1

Create BST Node Structure and Build Tree

Create a struct called Node with an int data field and two pointers left and right to Node. Then create nodes with these exact values and connections: root node with data = 15, left child 10, right child 20, left child of 10 is 8, right child of 10 is 12, left child of 20 is 17, right child of 20 is 25.

DSA C

// Define struct Node and create the BST nodes with exact values and connections
// Your code here

Hint

Start by defining the Node struct with data, left, and right. Then create each node as a variable and link them by setting the left and right pointers.

2

Create a Pointer to the Root Node

Create a pointer variable called root and set it to point to the node with data = 15.

DSA C

#include 
#include 

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

int main() {
    Node n15 = {15, NULL, NULL};
    Node n10 = {10, NULL, NULL};
    Node n20 = {20, NULL, NULL};
    Node n8 = {8, NULL, NULL};
    Node n12 = {12, NULL, NULL};
    Node n17 = {17, NULL, NULL};
    Node n25 = {25, NULL, NULL};

    n15.left = &n10;
    n15.right = &n20;
    n10.left = &n8;
    n10.right = &n12;
    n20.left = &n17;
    n20.right = &n25;

    // Create a pointer called root and set it to &n15
    // Your code here
    return 0;
}

Hint

Use Node* root = &n15; to create a pointer to the root node.

3

Write Function to Find Maximum Element in BST

Write a function called findMax that takes a pointer to Node called root and returns the maximum integer value in the BST. Traverse to the rightmost node and return its data.

DSA C

#include 
#include 

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

int findMax(Node* root) {
    // Traverse to the rightmost node and return its data
    // Your code here
}

int main() {
    Node n15 = {15, NULL, NULL};
    Node n10 = {10, NULL, NULL};
    Node n20 = {20, NULL, NULL};
    Node n8 = {8, NULL, NULL};
    Node n12 = {12, NULL, NULL};
    Node n17 = {17, NULL, NULL};
    Node n25 = {25, NULL, NULL};

    n15.left = &n10;
    n15.right = &n20;
    n10.left = &n8;
    n10.right = &n12;
    n20.left = &n17;
    n20.right = &n25;

    Node* root = &n15;

    return 0;
}

Hint

Use a while loop to move to the right child until it is NULL. Then return the data of that node.

4

Print the Maximum Element

Call the findMax function with root and print the returned maximum value using printf.

DSA C

#include 
#include 

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

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

int main() {
    Node n15 = {15, NULL, NULL};
    Node n10 = {10, NULL, NULL};
    Node n20 = {20, NULL, NULL};
    Node n8 = {8, NULL, NULL};
    Node n12 = {12, NULL, NULL};
    Node n17 = {17, NULL, NULL};
    Node n25 = {25, NULL, NULL};

    n15.left = &n10;
    n15.right = &n20;
    n10.left = &n8;
    n10.right = &n12;
    n20.left = &n17;
    n20.right = &n25;

    Node* root = &n15;

    // Call findMax and print the result
    // Your code here
    return 0;
}

Hint

Call findMax(root) and store the result in an int variable. Then use printf("%d\n", variable); to print the maximum value.

Practice

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

easy

A. At any leaf node

B. At the leftmost node

C. At the rightmost node

D. At the root 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 C

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 code snippets correctly finds the maximum element in a BST?

easy

A. while(root->left != NULL) root = root->left; return root->data;

B. while(root->right != NULL) root = root->right; return root->data;

C. if(root == NULL) return INT_MIN; return root->data;

D. return root->data;

Solution

1. Step 1: Analyze code logic

   while(root->right != NULL) root = root->right; return root->data; moves right until no right child exists, which is correct for max in BST.

2. Step 2: Check other options

   while(root->left != NULL) root = root->left; return root->data; moves left (minimum), C returns root data without traversal, D returns root data directly.

3. Final Answer:

   while(root->right != NULL) root = root->right; return root->data; -> Option B

4. Quick Check:

   Traverse rightmost node for max [OK]

Hint: Traverse right child until NULL to find max [OK]

Common Mistakes:

• Traversing left child instead of right
• Returning root data without traversal
• Not checking for NULL pointers

3. What will be the output of the following code snippet that finds the maximum element in a BST?

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

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

// BST structure:
//       10
//      /  \
//     5    20
//         /  \
//        15   30

int main() {
  // Assume BST is created as above
  printf("%d", findMax(root));
  return 0;
}

medium

A. 30

B. 20

C. 15

D. 10

Solution

1. Step 1: Understand BST structure

   The rightmost node is 30, which is the maximum element.

2. Step 2: Trace findMax function

   The function moves right from root (10) to 20, then to 30, stops as 30->right is NULL, returns 30.

3. Final Answer:

   30 -> Option A

4. Quick Check:

   Max element = 30 [OK]

Hint: Max is rightmost node: 10 -> 20 -> 30 [OK]

Common Mistakes:

• Returning root data without traversal
• Confusing max with root or left child
• Not following right pointers correctly

4. Identify the error in the following C function that is supposed to find the maximum element in a BST:

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

medium

A. It returns -1 for empty tree instead of INT_MIN

B. It should use recursion instead of loop

C. It does not check if root is NULL before accessing data

D. It traverses left instead of right to find maximum

Solution

1. Step 1: Analyze traversal direction

   The function moves left to find max, but max is at rightmost node in BST.

2. Step 2: Check other issues

   Returning -1 is acceptable for empty tree; checking root NULL is done; recursion is optional.

3. Final Answer:

   It traverses left instead of right to find maximum -> Option D

4. Quick Check:

   Max is rightmost, not leftmost [OK]

Hint: Max element is at rightmost, not leftmost node [OK]

Common Mistakes:

• Confusing left and right child traversal
• Ignoring NULL checks
• Thinking recursion is mandatory

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?

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

What is the output if the BST has nodes with values: 10, 20, 20, 30 (duplicates on right)?

hard

A. 30

B. 20

C. 10

D. Error due to duplicates

Solution

1. Step 1: Understand duplicates in BST

   Duplicates allowed on right means equal values go to right subtree, so max is still rightmost node.

2. Step 2: Trace findMax with duplicates

   Traversal moves right from 10 to 20, then to next 20, then to 30, which is rightmost and max.

3. Final Answer:

   30 -> Option A

4. Quick Check:

   Duplicates on right do not affect max = rightmost node [OK]

Hint: Duplicates on right subtree keep max at rightmost node [OK]

Common Mistakes:

• Assuming duplicates cause errors
• Stopping at first duplicate value
• Confusing duplicates location in BST