BST Find Minimum Element in DSA Javascript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Binary Search Tree (BST)?

A BST is a tree where each node has at most two children. The left child's value is less than the parent's value, and the right child's value is greater. This helps in fast searching.

beginner

How do you find the minimum element in a BST?

Start at the root and keep moving to the left child until there is no left child. The last node you reach is the minimum element.

beginner

Why does moving left in a BST lead to the minimum element?

Because in a BST, left children always have smaller values than their parents, so the leftmost node holds the smallest value.

intermediate

What is the time complexity of finding the minimum element in a BST?

The time complexity is O(h), where h is the height of the tree. In the best case (balanced tree), it's O(log n), and in the worst case (skewed tree), it's O(n).

beginner

Show the JavaScript code snippet to find the minimum element in a BST.

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

In a BST, where is the minimum element located?

A At the leftmost node

B At the rightmost node

C At the root node

D At any leaf node

The minimum element is always at the leftmost node because left children have smaller values.

What should you do if the BST is empty when finding the minimum element?

A Throw an error

B Return the root value

C Return zero

D Return null or indicate no minimum

If the BST is empty (root is null), there is no minimum element, so return null.

What is the time complexity to find the minimum element in a balanced BST with n nodes?

A O(log n)

B O(n log n)

C O(1)

D O(n)

In a balanced BST, height h is about log n, so finding minimum takes O(log n) time.

Which of these steps is NOT part of finding the minimum element in a BST?

A Start at the root

B Keep moving to the right child

C Stop when no left child exists

D Return the last node's value

You move to the left child to find the minimum, not the right.

What does the function return if the BST has only one node?

A The value of the root's left child

B null

C The value of the single node

D Undefined

If there is only one node, it is the minimum, so the function returns its value.

Explain step-by-step how to find the minimum element in a Binary Search Tree.

Think about how BST organizes smaller values on the left.

Write a simple JavaScript function to find the minimum element in a BST and explain how it works.

Use a while loop to move left until no more left child.

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