BST Find Minimum Element in DSA Javascript - 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 when you want to quickly find the minimum value in a sorted structure.

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

📋 What You'll Learn

Create a BST with the exact nodes: 15, 10, 20, 8, 12, 17, 25

Create a function called findMin that finds the minimum value in the BST

Print the minimum value found by findMin

💡 Why This Matters

🌍 Real World

Finding minimum or maximum values quickly is useful in many applications like databases, search engines, and games where sorted data is stored in trees.

💼 Career

Understanding BST operations is important for software developers working with data structures, algorithms, and performance optimization.

1

Create BST Node class and build the tree

Create a class called Node with value, left, and right properties. Then create the BST by making nodes with these exact values and linking them to form this tree:

15 as root, 10 as left child of 15, 20 as right child of 15, 8 as left child of 10, 12 as right child of 10, 17 as left child of 20, 25 as right child of 20.

DSA Javascript

// Create Node class and build the BST with given nodes
// Your code here

Hint

Define a class with constructor for value, left, and right. Then create nodes and link them as left or right children exactly as described.

2

Create a function to find the minimum value

Create a function called findMin that takes the root node of the BST as input. It should return the smallest value by moving left until no more left child exists.

DSA Javascript

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

const root = new Node(15);
root.left = new Node(10);
root.right = new Node(20);
root.left.left = new Node(8);
root.left.right = new Node(12);
root.right.left = new Node(17);
root.right.right = new Node(25);

// Create function findMin(root) to find minimum value
// Your code here

Hint

Start from root and keep moving to the left child until left is null. Then return the current node's value.

3

Call the function to find minimum

Call the findMin function with root as argument and store the result in a variable called minValue.

DSA Javascript

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

const root = new Node(15);
root.left = new Node(10);
root.right = new Node(20);
root.left.left = new Node(8);
root.left.right = new Node(12);
root.right.left = new Node(17);
root.right.right = new Node(25);

function findMin(root) {
    let current = root;
    while (current.left !== null) {
        current = current.left;
    }
    return current.value;
}

// Call findMin(root) and store result in minValue
// Your code here

Hint

Use const minValue = findMin(root); to call the function and save the result.

4

Print the minimum value

Print the value stored in minValue using console.log.

DSA Javascript

class Node {
    constructor(value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

const root = new Node(15);
root.left = new Node(10);
root.right = new Node(20);
root.left.left = new Node(8);
root.left.right = new Node(12);
root.right.left = new Node(17);
root.right.right = new Node(25);

function findMin(root) {
    let current = root;
    while (current.left !== null) {
        current = current.left;
    }
    return current.value;
}

const minValue = findMin(root);

// Print minValue using console.log
// Your code here

Hint

Use console.log(minValue); to print the minimum value.

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.

3. Final Answer:

   At the leftmost node -> Option C

4. Quick Check:

   Minimum = leftmost node [OK]

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

Common Mistakes:

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

2. Which of the following JavaScript code snippets correctly finds the minimum element in a BST node structure where each node has left and value properties?

easy

A. function findMin(node) { while(node.left) { node = node.left; } return node.value; }

B. function findMin(node) { while(node.right) { node = node.right; } return node.value; }

C. function findMin(node) { return node.value; }

D. function findMin(node) { if(node.right) return findMin(node.right); else return node.value; }

Solution

1. Step 1: Check traversal direction

   Minimum is found by moving left, so loop should check node.left.

2. Step 2: Verify code correctness

   function findMin(node) { while(node.left) { node = node.left; } return node.value; } loops while node.left exists, then returns node.value, which is correct.

3. Final Answer:

   function findMin(node) { while(node.left) { node = node.left; } return node.value; } -> Option A

4. Quick Check:

   Traverse left until no left child [OK]

Hint: Loop left child nodes to find minimum [OK]

Common Mistakes:

• Looping right child instead of left
• Returning node.value without traversal
• Recursing on right child for minimum

3. Given the BST below and the function findMin that finds the minimum value, what will be the output?

const root = {
  value: 10,
  left: { value: 5, left: { value: 2, left: null, right: null }, right: null },
  right: { value: 15, left: null, right: null }
};

function findMin(node) {
  while(node.left) {
    node = node.left;
  }
  return node.value;
}

console.log(findMin(root));

medium

A. 15

B. 5

C. 10

D. 2

Solution

1. Step 1: Trace left children from root

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

2. Step 2: Return value of leftmost node

   Leftmost node is 2, so function returns 2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Leftmost node value = 2 [OK]

Hint: Minimum is leftmost node value 2 here [OK]

Common Mistakes:

• Returning root value instead of leftmost
• Confusing left and right child traversal
• Misreading tree structure

4. The following code is intended to find the minimum value in a BST but has a bug. What is the bug?

function findMin(node) {
  while(node.right) {
    node = node.right;
  }
  return node.value;
}

medium

A. It incorrectly traverses right child instead of left

B. It does not return the node value

C. It causes infinite loop

D. It throws syntax error

Solution

1. Step 1: Analyze traversal direction

   The code moves to node.right repeatedly, which finds the maximum, not minimum.

2. Step 2: Identify correct traversal for minimum

   Minimum requires moving to node.left, so the bug is wrong direction.

3. Final Answer:

   It incorrectly traverses right child instead of left -> Option A

4. Quick Check:

   Minimum = leftmost, not rightmost [OK]

Hint: Minimum is leftmost, not rightmost traversal [OK]

Common Mistakes:

• Confusing left and right child traversal
• Assuming right child leads to minimum
• Not testing code with example trees

5. You want to find the minimum element in a BST that may be empty (null). Which of the following improved functions correctly handles this edge case and returns null if the tree is empty?

hard

A. function findMin(node) { while(node.left) { node = node.left; } return node.value; }

B. function findMin(node) { if(!node) return null; while(node.left) { node = node.left; } return node.value; }

C. function findMin(node) { if(node.left) return findMin(node.left); else return node.value; }

D. function findMin(node) { if(!node.left) return null; else return findMin(node.left); }

Solution

1. Step 1: Check for empty tree

   function findMin(node) { if(!node) return null; while(node.left) { node = node.left; } return node.value; } returns null immediately if node is null, handling empty tree.

2. Step 2: Traverse left children safely

   Then it loops left until no left child, returning minimum value correctly.

3. Final Answer:

   function findMin(node) { if(!node) return null; while(node.left) { node = node.left; } return node.value; } -> Option B

4. Quick Check:

   Check null first, then traverse left [OK]

Hint: Check for null before traversal to avoid errors [OK]

Common Mistakes:

• Not checking for null input
• Returning null incorrectly when node exists
• Recursing without base case for null