BST Find Minimum Element in DSA C# - Build from Scratch

BST Find Minimum Element

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers. You want to find the smallest number in this tree. This is useful in many real-life cases, like finding the earliest date or the lowest price.

🎯 Goal: Build a simple BST with given numbers, then write code to find and print the minimum element in the BST.

📋 What You'll Learn

Create a BST node class with integer value and left/right child nodes

Insert given numbers into the BST in the given order

Write a method to find the minimum element in the BST

Print the minimum element found

💡 Why This Matters

🌍 Real World

Finding minimum or maximum values quickly is useful in many applications like scheduling, pricing, and searching data.

💼 Career

Understanding BSTs and how to find minimum/maximum values is a common task in software development and technical interviews.

1

Create BST Node Class and Insert Nodes

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 values in order: 20, 10, 30, 5, 15 using the Insert method.

DSA C#

// Define Node class
// Create root node and insert values 20, 10, 30, 5, 15
// Your code here

Hint

Think of the BST as a family tree. Each node can have a left child (smaller) and a right child (bigger). Insert values by comparing and going left or right.

2

Add Method to Find Minimum Element

Add a method called FindMin inside the Node class that returns the minimum integer value in the BST by always going to the left child until it is null.

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 FindMin method here
    // Your code here
}

Node root = new Node(20);
root.Insert(10);
root.Insert(30);
root.Insert(5);
root.Insert(15);

Hint

In a BST, the smallest value is always the leftmost node. Keep going left until no more left child exists.

3

Call FindMin Method on Root

Create an integer variable called minValue and set it to the result of calling FindMin() 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 FindMin()
    {
        if (Left == null) return Value;
        else return Left.FindMin();
    }
}

Node root = new Node(20);
root.Insert(10);
root.Insert(30);
root.Insert(5);
root.Insert(15);

// Create minValue variable and assign FindMin() result
// Your code here

Hint

Call the FindMin() method on the root node and save the result in minValue.

4

Print the Minimum Value

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

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 FindMin()
    {
        if (Left == null) return Value;
        else return Left.FindMin();
    }
}

Node root = new Node(20);
root.Insert(10);
root.Insert(30);
root.Insert(5);
root.Insert(15);

int minValue = root.FindMin();

// Print minValue
// Your code here

Hint

Use Console.WriteLine(minValue); to print the smallest value found in the BST.

Practice

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

easy

A. At the rightmost node

B. At the root 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 than their parents.

2. Step 2: Locate minimum element

   The smallest value is found by going as far left as possible from the root.

3. Final Answer:

   At the leftmost node -> Option C

4. Quick Check:

   Minimum element = leftmost node [OK]

Hint: Minimum is always the leftmost node in BST [OK]

Common Mistakes:

• Thinking minimum is at root always
• Confusing leftmost with rightmost node
• Assuming minimum can be any leaf

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

easy

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

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

C. return root.Value;

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

Solution

1. Step 1: Check loop condition for minimum

   Minimum is found by moving left while left child exists.

2. Step 2: Validate code correctness

   while (root.Left != null) { root = root.Left; } return root.Value; moves left until null, then returns last node's value correctly.

3. Final Answer:

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

4. Quick Check:

   Traverse left until null, then return value [OK]

Hint: Traverse left child until null to find minimum [OK]

Common Mistakes:

• Traversing right child instead of left
• Returning root value without traversal
• Looping until root is null causing error

3. What will be the output of the following C# code snippet?

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

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

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

medium

A. 7

B. 2

C. 5

D. 10

Solution

1. Step 1: Trace the tree structure

   Root is 10, left child 5, left-left child 2, left-right child 7.

2. Step 2: Follow the loop to find minimum

   Loop moves from 10 to 5, then to 2 (leftmost node). 2 has no left child, loop stops.

3. Final Answer:

   2 -> Option B

4. Quick Check:

   Leftmost node value = 2 [OK]

Hint: Leftmost node value is printed after loop [OK]

Common Mistakes:

• Printing root value instead of leftmost
• Confusing left-right child as minimum
• Stopping loop too early

4. Identify the error in the following C# method to find the minimum element in a BST:

int FindMin(Node root) {
  while (root != null) {
    root = root.Left;
  }
  return root.Value;
}

medium

A. The method should check root.Right instead of root.Left

B. The method should return root.Left.Value instead of root.Value

C. The method should use recursion instead of a loop

D. The loop condition should be root.Left != null, not root != null

Solution

1. Step 1: Analyze loop condition

   Loop runs while root is not null, but root becomes null after last left move.

2. Step 2: Identify cause of error

   After loop, root is null, so accessing root.Value causes error. Condition should be root.Left != null to stop at last node.

3. Final Answer:

   The loop condition should be root.Left != null, not root != null -> Option D

4. Quick Check:

   Stop before null to access valid node [OK]

Hint: Loop until root.Left is null, not root itself [OK]

Common Mistakes:

• Looping until root is null causing null reference
• Returning value after root becomes null
• Checking right child instead of left

5. Given a BST where some nodes have duplicate values, which approach correctly finds the minimum element considering duplicates are allowed only on the right subtree?

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

// Duplicates go to right subtree

Which code snippet correctly finds the minimum element?

hard

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

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

C. return root.Value; // root is minimum due to duplicates on right

D. while (root.Left != null && root.Left.Value < root.Value) { root = root.Left; } return root.Value;

Solution

1. Step 1: Understand duplicate placement rule

   Duplicates go to right subtree, so minimum is still in leftmost path.

2. Step 2: Confirm traversal for minimum

   Traverse left child nodes until no more left child exists to find minimum.

3. Final Answer:

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

4. Quick Check:

   Minimum is leftmost node even with duplicates on right [OK]

Hint: Duplicates on right don't affect leftmost minimum [OK]

Common Mistakes:

• Checking right subtree for minimum
• Assuming root is minimum without traversal
• Adding extra conditions unnecessarily