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 useful when you want to know the highest value stored in your data quickly.

🎯 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 class with integer value and left/right children

Insert given numbers into the BST in the given order

Write a method to find the maximum element in the BST

Print the maximum element found

💡 Why This Matters

🌍 Real World

Finding the maximum value in a BST is useful in databases, search engines, and any system that needs quick access to the highest value stored.

💼 Career

Understanding BST operations like insertion and finding maximum values is fundamental for software developers working with data structures and algorithms.

1

Create BST Node and Insert Numbers

Create a class called Node with an integer Value and two Node references called Left and Right. Then create a Node variable called root and insert these numbers in order: 15, 10, 20, 8, 12, 17, 25. Use a method called Insert to add nodes to the BST.

DSA C#

// Define Node class and Insert method
// Create root and insert nodes
// Your code here

Hint

Start by defining the Node class with its properties and constructor. Then write the Insert method to add new values correctly to the left or right subtree. Finally, create the root node and insert the given numbers one by one.

2

Create Method to Find Maximum Element

Add a method called FindMax inside the Node class that returns an integer. This method should find the maximum value in the BST by moving to the right child until it reaches the rightmost node.

DSA C#

public class Node
{
    public int Value;
    public Node Left;
    public Node Right;

    public Node(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }

    public void Insert(int newValue)
    {
        if (newValue < Value)
        {
            if (Left == null) Left = new Node(newValue);
            else Left.Insert(newValue);
        }
        else
        {
            if (Right == null) Right = new Node(newValue);
            else Right.Insert(newValue);
        }
    }

    // Add FindMax method here
    // Your code here
}

Node root = new Node(15);
root.Insert(10);
root.Insert(20);
root.Insert(8);
root.Insert(12);
root.Insert(17);
root.Insert(25);

Hint

To find the maximum, start from the current node and keep moving to the right child until there is no right child left. Then return the value of that node.

3

Call FindMax Method

Create an integer variable called maxValue and set it to the result of calling FindMax on the root node.

DSA C#

public class Node
{
    public int Value;
    public Node Left;
    public Node Right;

    public Node(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }

    public void Insert(int newValue)
    {
        if (newValue < Value)
        {
            if (Left == null) Left = new Node(newValue);
            else Left.Insert(newValue);
        }
        else
        {
            if (Right == null) Right = new Node(newValue);
            else Right.Insert(newValue);
        }
    }

    public int FindMax()
    {
        Node current = this;
        while (current.Right != null)
        {
            current = current.Right;
        }
        return current.Value;
    }
}

Node root = new Node(15);
root.Insert(10);
root.Insert(20);
root.Insert(8);
root.Insert(12);
root.Insert(17);
root.Insert(25);

// Create maxValue variable and call FindMax
// Your code here

Hint

Simply call FindMax() on the root node and store the result in maxValue.

4

Print the Maximum Element

Write a Console.WriteLine statement to print the value of maxValue.

DSA C#

public class Node
{
    public int Value;
    public Node Left;
    public Node Right;

    public Node(int value)
    {
        Value = value;
        Left = null;
        Right = null;
    }

    public void Insert(int newValue)
    {
        if (newValue < Value)
        {
            if (Left == null) Left = new Node(newValue);
            else Left.Insert(newValue);
        }
        else
        {
            if (Right == null) Right = new Node(newValue);
            else Right.Insert(newValue);
        }
    }

    public int FindMax()
    {
        Node current = this;
        while (current.Right != null)
        {
            current = current.Right;
        }
        return current.Value;
    }
}

Node root = new Node(15);
root.Insert(10);
root.Insert(20);
root.Insert(8);
root.Insert(12);
root.Insert(17);
root.Insert(25);

int maxValue = root.FindMax();

// Print maxValue
// Your code here

Hint

Use Console.WriteLine(maxValue); to print the maximum value found in the BST.

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