BST Find Minimum Element in DSA Java - Build from Scratch

BST Find Minimum Element

📖 Scenario: You are working with a simple phone book application that stores contacts in a Binary Search Tree (BST). Each contact has a unique phone number. You want to find the contact with the smallest phone number to quickly access the earliest saved contact.

🎯 Goal: Build a Java program that creates a BST with given phone numbers, then finds and prints the minimum phone number stored in the BST.

📋 What You'll Learn

Create a BST node class with integer phone number data and left/right child references

Insert given phone numbers into the BST

Write a method to find the minimum phone number in the BST

Print the minimum phone number found

💡 Why This Matters

🌍 Real World

Phone books, contact lists, and databases often use BSTs to store and quickly access sorted data like phone numbers.

💼 Career

Understanding BSTs and how to find minimum or maximum values is essential for software engineers working with data structures and algorithms in real-world applications.

1

Create BST Node Class and Insert Phone Numbers

Create a class called Node with an integer variable phoneNumber, and two Node references called left and right. Then create a class called BST with a Node variable called root. In the BST class, write a method called insert that takes an integer phoneNumber and inserts it into the BST following BST rules. Insert these exact phone numbers into the BST in this order: 5551234, 5555678, 5550001, 5554321, 5551111.

DSA Java

// Define Node class and BST class with insert method
// Insert phone numbers 5551234, 5555678, 5550001, 5554321, 5551111
// Your code here

Hint

Remember, each node stores a phone number and references to left and right child nodes. Insert smaller numbers to the left, larger to the right.

2

Add Method to Find Minimum Phone Number

In the BST class, add a method called findMin that returns the minimum phone number stored in the BST. This method should start from the root and keep moving to the left child until it reaches the leftmost node, then return that node's phoneNumber.

DSA Java

class Node {
    int phoneNumber;
    Node left, right;

    Node(int phoneNumber) {
        this.phoneNumber = phoneNumber;
        left = right = null;
    }
}

class BST {
    Node root;

    BST() {
        root = null;
    }

    void insert(int phoneNumber) {
        root = insertRec(root, phoneNumber);
    }

    Node insertRec(Node root, int phoneNumber) {
        if (root == null) {
            root = new Node(phoneNumber);
            return root;
        }
        if (phoneNumber  root.phoneNumber) {
            root.right = insertRec(root.right, phoneNumber);
        }
        return root;
    }

    int findMin() {
        // Your code here
    }

    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(5551234);
        tree.insert(5555678);
        tree.insert(5550001);
        tree.insert(5554321);
        tree.insert(5551111);
    }
}

Hint

Start from the root and keep moving left until there is no left child. The leftmost node holds the smallest phone number.

3

Call findMin Method and Store Result

In the main method, call the findMin method on the tree object and store the returned minimum phone number in an integer variable called minPhoneNumber.

DSA Java

class Node {
    int phoneNumber;
    Node left, right;

    Node(int phoneNumber) {
        this.phoneNumber = phoneNumber;
        left = right = null;
    }
}

class BST {
    Node root;

    BST() {
        root = null;
    }

    void insert(int phoneNumber) {
        root = insertRec(root, phoneNumber);
    }

    Node insertRec(Node root, int phoneNumber) {
        if (root == null) {
            root = new Node(phoneNumber);
            return root;
        }
        if (phoneNumber  root.phoneNumber) {
            root.right = insertRec(root.right, phoneNumber);
        }
        return root;
    }

    int findMin() {
        Node current = root;
        while (current.left != null) {
            current = current.left;
        }
        return current.phoneNumber;
    }

    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(5551234);
        tree.insert(5555678);
        tree.insert(5550001);
        tree.insert(5554321);
        tree.insert(5551111);
        // Store minimum phone number below
        // Your code here
    }
}

Hint

Call findMin() on the tree object and save the result in minPhoneNumber.

4

Print the Minimum Phone Number

In the main method, print the value of the minPhoneNumber variable using System.out.println.

DSA Java

class Node {
    int phoneNumber;
    Node left, right;

    Node(int phoneNumber) {
        this.phoneNumber = phoneNumber;
        left = right = null;
    }
}

class BST {
    Node root;

    BST() {
        root = null;
    }

    void insert(int phoneNumber) {
        root = insertRec(root, phoneNumber);
    }

    Node insertRec(Node root, int phoneNumber) {
        if (root == null) {
            root = new Node(phoneNumber);
            return root;
        }
        if (phoneNumber  root.phoneNumber) {
            root.right = insertRec(root.right, phoneNumber);
        }
        return root;
    }

    int findMin() {
        Node current = root;
        while (current.left != null) {
            current = current.left;
        }
        return current.phoneNumber;
    }

    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(5551234);
        tree.insert(5555678);
        tree.insert(5550001);
        tree.insert(5554321);
        tree.insert(5551111);
        int minPhoneNumber = tree.findMin();
        // Print the minimum phone number below
        // Your code here
    }
}

Hint

Use System.out.println(minPhoneNumber); to print the minimum phone number.

Practice

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

easy

A. At the leftmost node

B. At the rightmost node

C. At the root 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 moving left until no more left child exists.

3. Final Answer:

   At the leftmost node -> Option A

4. Quick Check:

   Minimum = leftmost node [OK]

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

Common Mistakes:

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

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

easy

A. while(root.right != null) { root = root.right; } return root.data;

B. while(root.left != null) { root = root.left; } return root.data;

C. if(root == null) return Integer.MAX_VALUE; return root.data;

D. return root.data;

Solution

1. Step 1: Check loop condition for minimum

   Minimum is found by moving left while left child exists.

2. Step 2: Verify code correctness

   while(root.left != null) { root = root.left; } return root.data; moves left until left child is null, then returns data.

3. Final Answer:

   while(root.left != null) { root = root.left; } return root.data; -> Option B

4. Quick Check:

   Loop left until null, then return [OK]

Hint: Traverse left children until none left [OK]

Common Mistakes:

• Traversing right child instead of left
• Returning root data without traversal
• Ignoring null root check

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

class Node {
  int data;
  Node left, right;
  Node(int d) { data = d; left = right = null; }
}

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;
}
System.out.println(current.data);

medium

A. 2

B. 7

C. 5

D. 10

Solution

1. Step 1: Trace the tree structure

   Root=10, left=5, right=15, left.left=2, left.right=7.

2. Step 2: Follow while loop to find minimum

   Start at 10, move left to 5, then left to 2, which has no left child.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Leftmost node data = 2 [OK]

Hint: Output is leftmost node's data after loop [OK]

Common Mistakes:

• Printing root data instead of leftmost
• Confusing left and right traversal
• Stopping loop too early

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

public int findMin(Node root) {
  if(root == null) return -1;
  while(root.right != null) {
    root = root.right;
  }
  return root.data;
}

medium

A. Method should be void, not int

B. Should return -1 only if root is leaf

C. Should check for root.data == null

D. Should traverse left child, not right child

Solution

1. Step 1: Analyze traversal direction

   Minimum element is found by moving left, not right.

2. Step 2: Identify correct traversal

   Loop should check root.left != null and move root = root.left.

3. Final Answer:

   Should traverse left child, not right child -> Option D

4. Quick Check:

   Minimum = leftmost node, so traverse left [OK]

Hint: Minimum is leftmost, so traverse left child [OK]

Common Mistakes:

• Traversing right child instead of left
• Returning -1 incorrectly
• Checking data for null instead of node

5. Given a BST where some nodes have duplicate values, which approach correctly finds the minimum unique element?

public int findMinUnique(Node root) {
  Set<Integer> seen = new HashSet<>();
  int min = Integer.MAX_VALUE;
  while(root != null) {
    if(!seen.contains(root.data)) {
      min = Math.min(min, root.data);
      seen.add(root.data);
    }
    root = root.left;
  }
  return min;
}

What is the main issue with this method?

hard

A. It uses a HashSet unnecessarily for BST

B. It does not handle empty tree correctly

C. It only checks left children, missing other nodes

D. It returns max value instead of min

Solution

1. Step 1: Understand traversal logic

   Method only moves down left children, ignoring right subtree.

2. Step 2: Identify missed nodes

   Duplicates or unique values in right subtree are missed.

3. Step 3: Correct approach

   To find minimum unique, full tree traversal (e.g., inorder) is needed.

4. Final Answer:

   It only checks left children, missing other nodes -> Option C

5. Quick Check:

   Partial traversal misses right subtree [OK]

Hint: Traverse entire tree to find minimum unique value [OK]

Common Mistakes:

• Assuming left path covers all nodes
• Ignoring duplicates in right subtree
• Using HashSet without full traversal