BST Find Maximum Element in DSA C++

Mental Model

In a Binary Search Tree, the biggest number is always the rightmost node. We just keep going right until we can't go further.

Analogy: Imagine a line of boxes arranged from smallest on the left to biggest on the right. To find the biggest box, you just walk to the rightmost box in the line.

      10
     /  \
    5    15
          \
           20
            \
             25

Start at root (10) and keep moving right to find max.

Dry Run Walkthrough

Input: BST with nodes: 10 -> 5 (left), 15 (right), 15 -> 20 (right), 20 -> 25 (right)

Goal: Find the maximum element in the BST

Step 1: Start at root node 10

10 [curr->10] -> 5 (left), 15 (right)

Why: We begin at the root to find the maximum

Step 2: Move curr to right child 15

10 -> 15 [curr->15] -> 20 (right)

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

Step 3: Move curr to right child 20

10 -> 15 -> 20 [curr->20] -> 25 (right)

Why: Keep moving right to find bigger values

Step 4: Move curr to right child 25

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

Why: 25 has no right child, so it is the maximum

Result:

10 -> 15 -> 20 -> 25 [curr->25] -> null
Maximum element is 25

Annotated Code

DSA C++

#include <iostream>
#include <stdexcept>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

int findMax(Node* root) {
    if (root == nullptr) {
        throw runtime_error("Tree is empty");
    }
    Node* curr = root;
    while (curr->right != nullptr) {
        curr = curr->right; // advance curr to right child to find max
    }
    return curr->data; // curr is rightmost node, max value
}

int main() {
    Node* root = new Node(10);
    root->left = new Node(5);
    root->right = new Node(15);
    root->right->right = new Node(20);
    root->right->right->right = new Node(25);

    cout << "Maximum element is " << findMax(root) << endl;
    return 0;
}

while (curr->right != nullptr) {

keep moving curr to right child to find the maximum

curr = curr->right; // advance curr to right child to find max

advance curr pointer to next right node

return curr->data; // curr is rightmost node, max value

return the data of the rightmost node as maximum

Output

Maximum element is 25

Complexity Analysis

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

Space: O(1) because we use only a few pointers and no extra space proportional to input

vs Alternative: Compared to traversing all nodes (O(n)), this is faster as it uses BST property to go directly right

Edge Cases

Empty tree (root is nullptr)

Throws an error indicating the tree is empty

DSA C++

if (root == nullptr) { throw runtime_error("Tree is empty"); }

Tree with only one node

Returns that single node's value as maximum

DSA C++

while (curr->right != nullptr) { ... } // loop skipped if no right child

When to Use This Pattern

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

Common Mistakes

Mistake: Trying to find max by checking all nodes instead of just going right
Fix: Use the BST property and move only to the right child until null

Mistake: Not handling empty tree and causing null pointer errors
Fix: Add a check for root == nullptr and handle it properly

Summary

Finds the maximum element by moving to the rightmost node in the BST.

Use when you want the largest value in a BST quickly.

The maximum is always the rightmost node because BST nodes to the right are bigger.

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