BST Find Maximum Element in DSA C

Mental Model

In a Binary Search Tree, the biggest number is always found by going as far right as possible.

Analogy: Imagine a family tree where older generations are on the left and younger generations are on the right. The youngest person (maximum) is the one at the far right end of the tree.

      10
     /  \
    5    15
          \
           20
            \
             25
             ↑

Dry Run Walkthrough

Input: BST: 10 -> 5, 15 -> null, 20 -> null, 25 -> null; find max element

Goal: Find the largest value in the BST by moving right until no more right child exists

Step 1: Start at root node with value 10

10 [curr->] -> 5 -> null, 15 -> null -> 20 -> null -> 25 -> null

Why: We begin at the root to find the maximum

Step 2: Move curr to right child 15

10 -> 5 -> null, 15 [curr->] -> null -> 20 -> null -> 25 -> null

Why: Maximum is always in the right subtree, so move right

Step 3: Move curr to right child 20

10 -> 5 -> null, 15 -> null -> 20 [curr->] -> null -> 25 -> null

Why: Keep moving right to find bigger values

Step 4: Move curr to right child 25

10 -> 5 -> null, 15 -> null -> 20 -> null -> 25 [curr->] -> null

Why: Continue moving right to find the maximum

Step 5: No right child for 25, stop and return 25

10 -> 5 -> null, 15 -> null -> 20 -> null -> 25 [curr->] -> null

Why: No more right nodes means current node is maximum

Result:

10 -> 5 -> null, 15 -> null -> 20 -> null -> 25 [max] -> null
Maximum element found: 25

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure for BST
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// Create a new node
Node* newNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// Insert data into BST
Node* insert(Node* root, int data) {
    if (root == NULL) return newNode(data);
    if (data < root->data) root->left = insert(root->left, data);
    else root->right = insert(root->right, data);
    return root;
}

// Find maximum element in BST
int findMax(Node* root) {
    if (root == NULL) {
        printf("Tree is empty\n");
        return -1; // or some error code
    }
    Node* curr = root;
    while (curr->right != NULL) {
        curr = curr->right; // move right to find max
    }
    return curr->data; // rightmost node data is max
}

int main() {
    Node* root = NULL;
    root = insert(root, 10);
    root = insert(root, 5);
    root = insert(root, 15);
    root = insert(root, 20);
    root = insert(root, 25);

    int maxVal = findMax(root);
    printf("Maximum element found: %d\n", maxVal);
    return 0;
}

while (curr->right != NULL) {

advance curr to right child to find the largest value

curr = curr->right;

move curr pointer right to keep searching for max

return curr->data;

return data of rightmost node as maximum

Output

Maximum element found: 25

Complexity Analysis

Time: O(h) where h is the height of the tree because we only move right down the tree

Space: O(1) because we use only a few pointers and no extra data structures

vs Alternative: Compared to scanning all nodes (O(n)), this is faster because BST property lets us jump directly to max

Edge Cases

Empty tree

Prints 'Tree is empty' and returns -1

DSA C

if (root == NULL) { printf("Tree is empty\n"); return -1; }

Tree with single node

Returns that node's value as maximum

DSA C

while (curr->right != NULL) { curr = curr->right; }

When to Use This Pattern

When you need the largest value in a BST, look for the rightmost node by following right children until none remain.

Common Mistakes

Mistake: Trying to find max by checking both left and right subtrees recursively
Fix: Use the BST property and just follow right children until the end

Summary

Finds the largest value in a BST by moving right until no more right child exists.

Use when you want the maximum element quickly in a BST without searching all nodes.

The maximum is always the rightmost node in a BST.

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