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 family tree where the oldest person is always on the far right branch. To find the oldest, you just follow the right branches until you reach the end.

      10
     /  \
    5    15
          \
           20
            \
             25
↑ root

Dry Run Walkthrough

Input: BST with nodes 10, 5, 15, 20, 25; find maximum element

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

Step 1: Start at root node 10

10 -> right -> 15 -> right -> 20 -> right -> 25 -> null ↑ at 10

Why: We begin at the root to find the maximum by moving right

Step 2: Move right from 10 to 15

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

Why: Right child is bigger, so move right to find larger values

Step 3: Move right from 15 to 20

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

Why: Continue moving right to find bigger values

Step 4: Move right from 20 to 25

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

Why: Keep moving right until no more right child

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

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

Why: 25 is the rightmost node, so it is the maximum

Result:

10 -> 15 -> 20 -> 25 -> null
Maximum element found: 25

Annotated Code

DSA C#

using System;

class Node
{
    public int data;
    public Node left, right;

    public Node(int value)
    {
        data = value;
        left = right = null;
    }
}

class BST
{
    public Node root;

    public BST()
    {
        root = null;
    }

    public void Insert(int value)
    {
        root = InsertRec(root, value);
    }

    private Node InsertRec(Node root, int value)
    {
        if (root == null)
        {
            root = new Node(value);
            return root;
        }

        if (value < root.data)
            root.left = InsertRec(root.left, value);
        else
            root.right = InsertRec(root.right, value);

        return root;
    }

    public int FindMax()
    {
        if (root == null)
            throw new InvalidOperationException("BST is empty");

        Node current = root;
        while (current.right != null)
        {
            current = current.right; // move right to find bigger value
        }
        return current.data; // rightmost node data is max
    }
}

class Program
{
    static void Main()
    {
        BST tree = new BST();
        tree.Insert(10);
        tree.Insert(5);
        tree.Insert(15);
        tree.Insert(20);
        tree.Insert(25);

        int max = tree.FindMax();
        Console.WriteLine("Maximum element found: " + max);
    }
}

while (current.right != null) { current = current.right; // move right to find bigger value }

advance current pointer to the right child until no more right child exists

return current.data; // rightmost node data is max

return the data of the rightmost node as the maximum element

Output

Maximum element found: 25

Complexity Analysis

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

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

vs Alternative: Compared to traversing all nodes (O(n)), this approach is faster because it uses BST property to go directly to the max

Edge Cases

Empty BST

Throws an exception because there is no maximum in an empty tree

DSA C#

if (root == null)
            throw new InvalidOperationException("BST is empty");

BST with only one node

Returns that node's value as maximum

DSA C#

while (current.right != null)
        {
            current = current.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 traversing the entire tree instead of just going right
Fix: Use the BST property and move only to the right child until no more right child exists

Mistake: Not handling empty tree before searching max
Fix: Check if root is null and handle or throw exception before traversal

Summary

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

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

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 root node

B. At the rightmost node

C. At the leftmost node

D. At any leaf node

Solution

1. Step 1: Understand BST property

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

2. Step 2: Locate maximum element

   The maximum element is the largest value, so it must be the rightmost node because values increase to the right.

3. Final Answer:

   At the rightmost node -> Option B

4. Quick Check:

   Maximum element = rightmost node [OK]

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

Common Mistakes:

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

2. Which of the following C# code snippets correctly finds the maximum element in a BST node called root?

easy

A. while (root.Left != null) { root = root.Left; } return root.Value;

B. if (root.Left == null) return root.Value; else return root.Left.Value;

C. while (root.Right != null) { root = root.Right; } return root.Value;

D. return root.Value; // root is always max

Solution

1. Step 1: Check traversal direction

   To find max, traverse right child nodes until no more right child exists.

2. Step 2: Verify code correctness

   while (root.Right != null) { root = root.Right; } return root.Value; uses a while loop to move right until root.Right is null, then returns root.Value, which is correct.

3. Final Answer:

   while (root.Right != null) { root = root.Right; } return root.Value; -> Option C

4. Quick Check:

   Traverse right until null, then return value [OK]

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

Common Mistakes:

• Traversing left child instead of right
• Returning root value without traversal
• Using incorrect condition in loop

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

class Node {
  public int Value;
  public Node Left, Right;
  public Node(int val) { Value = val; Left = Right = null; }
}

Node root = new Node(10);
root.Left = new Node(5);
root.Right = new Node(15);
root.Right.Right = new Node(20);

Node current = root;
while (current.Right != null) {
  current = current.Right;
}
Console.WriteLine(current.Value);

medium

A. 5

B. 15

C. 10

D. 20

Solution

1. Step 1: Trace the BST structure

   Root is 10, right child 15, right child of 15 is 20. So rightmost node is 20.

2. Step 2: Follow the loop

   The loop moves current from 10 to 15, then to 20, then stops because 20.Right is null.

3. Final Answer:

   20 -> Option D

4. Quick Check:

   Rightmost node value = 20 [OK]

Hint: Rightmost node value is maximum [OK]

Common Mistakes:

• Stopping at 15 instead of 20
• Printing root value instead of max
• Confusing left and right children

4. The following C# method is intended to find the maximum element in a BST. What is the error?

int FindMax(Node root) {
  if (root == null) return int.MinValue;
  if (root.Right == null) return root.Value;
  return FindMax(root.Left);
}

medium

A. It should recurse on root.Right, not root.Left

B. It should return int.MaxValue when root is null

C. It should check root.Left instead of root.Right

D. No error, code is correct

Solution

1. Step 1: Analyze recursion direction

   To find max, recursion must go right, but code recurses left incorrectly.

2. Step 2: Identify correct recursion

   Change FindMax(root.Left) to FindMax(root.Right) to find max correctly.

3. Final Answer:

   It should recurse on root.Right, not root.Left -> Option A

4. Quick Check:

   Max found by right recursion [OK]

Hint: Max search recurses right child, not left [OK]

Common Mistakes:

• Recursing left child instead of right
• Returning wrong base case value
• Ignoring null root check

5. Given a BST where some nodes have duplicate values, which approach correctly finds the maximum value considering duplicates?

int FindMaxWithDuplicates(Node root) {
  if (root == null) return int.MinValue;
  int rightMax = FindMaxWithDuplicates(root.Right);
  return Math.Max(root.Value, rightMax);
}

What is the output of FindMaxWithDuplicates on this BST? Root: 10 Left: 5 Right: 10 Right.Right: 15 Right.Right.Right: 15

hard

A. 15

B. 10

C. 5

D. Error due to duplicates

Solution

1. Step 1: Understand duplicate handling

   The method compares current node value with max from right subtree, so duplicates do not affect max finding.

2. Step 2: Trace values

   Right subtree max is 15 (rightmost node). Root value 10 is less than 15, so max is 15.

3. Final Answer:

   15 -> Option A

4. Quick Check:

   Max value with duplicates = 15 [OK]

Hint: Compare node value with right subtree max for duplicates [OK]

Common Mistakes:

• Assuming duplicates cause errors
• Returning first max found without comparison
• Ignoring right subtree values