BST Find Maximum Element in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Find maximum element in a BST - Output after insertions

Given the following JavaScript code that inserts elements into a Binary Search Tree (BST) and finds the maximum element, what is the printed output?

DSA Javascript

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

class BST {
  constructor() {
    this.root = null;
  }

  insert(data) {
    const newNode = new Node(data);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (data < current.data) {
        if (!current.left) {
          current.left = newNode;
          break;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          break;
        }
        current = current.right;
      }
    }
  }

  findMax() {
    if (!this.root) return null;
    let current = this.root;
    while (current.right) {
      current = current.right;
    }
    return current.data;
  }
}

const bst = new BST();
bst.insert(15);
bst.insert(10);
bst.insert(20);
bst.insert(8);
bst.insert(12);
bst.insert(17);
bst.insert(25);
console.log(bst.findMax());

A 17

B 20

C 15

D 25

💡 Hint

The maximum element in a BST is the rightmost node.

In a BST, the maximum element is found by going as far right as possible from the root. Here, 25 is the rightmost node.

❓ Predict Output

intermediate

Output of findMax on empty BST

What is the output of the following code when findMax is called on an empty BST?

DSA Javascript

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

class BST {
  constructor() {
    this.root = null;
  }

  findMax() {
    if (!this.root) return null;
    let current = this.root;
    while (current.right) {
      current = current.right;
    }
    return current.data;
  }
}

const bst = new BST();
console.log(bst.findMax());

A null

B undefined

C 0

D Throws an error

💡 Hint

Check what findMax returns if root is null.

The method returns null explicitly if the tree is empty (root is null).

🔧 Debug

advanced

Identify the error in findMax method

What error will the following code produce when findMax is called on a BST with nodes?

DSA Javascript

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

class BST {
  constructor() {
    this.root = null;
  }

  findMax() {
    let current = this.root;
    while (current.right !== null) {
      current = current.right;
    }
    return current.data;
  }
}

const bst = new BST();
bst.insert(10);
bst.insert(20);
console.log(bst.findMax());

A TypeError: Cannot read property 'right' of null

B ReferenceError: bst.insert is not a function

C Output: 20

D SyntaxError: Unexpected token

💡 Hint

Check if insert method is defined in the BST class.

The BST class does not have an insert method defined, so calling bst.insert causes a ReferenceError.

❓ Predict Output

advanced

Output after removing maximum element

Given the BST and the removeMax method below, what is the output of findMax after removing the maximum element?

DSA Javascript

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

class BST {
  constructor() {
    this.root = null;
  }

  insert(data) {
    const newNode = new Node(data);
    if (!this.root) {
      this.root = newNode;
      return;
    }
    let current = this.root;
    while (true) {
      if (data < current.data) {
        if (!current.left) {
          current.left = newNode;
          break;
        }
        current = current.left;
      } else {
        if (!current.right) {
          current.right = newNode;
          break;
        }
        current = current.right;
      }
    }
  }

  findMax() {
    if (!this.root) return null;
    let current = this.root;
    while (current.right) {
      current = current.right;
    }
    return current.data;
  }

  removeMax() {
    if (!this.root) return null;
    let parent = null;
    let current = this.root;
    while (current.right) {
      parent = current;
      current = current.right;
    }
    if (!parent) {
      this.root = current.left;
    } else {
      parent.right = current.left;
    }
    return current.data;
  }
}

const bst = new BST();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(12);
bst.insert(20);
bst.removeMax();
console.log(bst.findMax());

A 15

B 20

C 12

D null

💡 Hint

Removing max removes the rightmost node, so max changes to its parent or left child.

The maximum 20 is removed. The new maximum is the next rightmost node 15.

🧠 Conceptual

expert

Why is findMax efficient in a BST?

Why does the findMax method in a Binary Search Tree run efficiently compared to searching maximum in an unsorted binary tree?

A Because BST stores elements in a linked list fashion making maximum retrieval O(1).

B Because BST uses hashing internally to find maximum quickly.

C Because BST stores elements so that the maximum is always the rightmost node, allowing direct traversal without checking all nodes.

D Because BST sorts elements after every insertion, so maximum is at the root.

💡 Hint

Think about the BST property and how it organizes data.

BST property ensures all right children are greater, so maximum is found by going right until no more right child exists, making it efficient.

Practice

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

easy

A. At any leaf node

B. At the leftmost node

C. At the root node

D. At the rightmost node

Solution

1. Step 1: Understand BST property

   In a BST, left child nodes have smaller values and right child nodes have larger values than their parent.

2. Step 2: Locate maximum element

   The maximum element is the largest value, so it must be the rightmost node in the tree.

3. Final Answer:

   At the rightmost node -> Option D

4. Quick Check:

   Maximum = 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 JavaScript code snippets correctly finds the maximum element in a BST node structure where each node has left and right properties?

easy

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

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

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

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

Solution

1. Step 1: Check traversal direction

   To find maximum, we must move right until no more right child exists.

2. Step 2: Verify code correctness

   function findMax(node) { while(node.right) { node = node.right; } return node.value; } correctly loops while node.right exists, then returns node.value.

3. Final Answer:

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

4. Quick Check:

   Traverse rightmost node to get max [OK]

Hint: Loop right child until none to find max [OK]

Common Mistakes:

• Looping left child instead of right
• Returning root value without traversal
• Recursing incorrectly on left child

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

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

const root = new Node(10);
root.left = new Node(5);
root.right = new Node(15);
root.right.right = new Node(20);

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

console.log(findMax(root));

medium

A. 20

B. 10

C. 15

D. 5

Solution

1. Step 1: Trace the tree structure

   Root is 10, right child 15, right of 15 is 20. The rightmost node is 20.

2. Step 2: Follow findMax function

   The function moves right until no right child. It stops at node with value 20 and returns it.

3. Final Answer:

   20 -> Option A

4. Quick Check:

   Rightmost node value = 20 [OK]

Hint: Output is value of rightmost node [OK]

Common Mistakes:

• Returning root value instead of max
• Confusing left and right children
• Not following loop to last right node

4. The following code is intended to find the maximum element in a BST but does not work correctly. What is the error?

function findMax(node) {
  if (!node.right) {
    return node.value;
  }
  return findMax(node.left);
}

medium

A. It should check node.left instead of node.right

B. It should return node.right.value instead of node.value

C. It should recurse on node.right, not node.left

D. It should use a loop instead of recursion

Solution

1. Step 1: Analyze recursion direction

   The code checks if node.right is null, then returns node.value. Otherwise, it recurses on node.left.

2. Step 2: Identify correct recursion path

   To find max, recursion must go right, not left. So it should recurse on node.right.

3. Final Answer:

   It should recurse on node.right, not node.left -> Option C

4. Quick Check:

   Max found by going right child [OK]

Hint: Recurse or loop right child to find max [OK]

Common Mistakes:

• Recursing left child instead of right
• Returning wrong node value
• Thinking loop is mandatory over recursion

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

function findMax(node) {
  while(node.right && node.right.value >= node.value) {
    node = node.right;
  }
  return node.value;
}

What is the main reason for the condition node.right.value >= node.value in the loop?

hard

A. To avoid infinite loops by stopping if right child is smaller

B. To move right only if the right child is greater or equal, handling duplicates correctly

C. To ensure the maximum is always strictly greater than current node

D. To skip nodes with equal values on the left subtree

Solution

1. Step 1: Understand duplicates in BST

   Duplicates allowed only on right subtree means equal values can appear on right child nodes.

2. Step 2: Analyze loop condition

   The loop moves right while right child exists and its value is greater or equal to current node, ensuring duplicates are included in max search.

3. Final Answer:

   To move right only if the right child is greater or equal, handling duplicates correctly -> Option B

4. Quick Check:

   Right child >= current node handles duplicates [OK]

Hint: Include equal right child to handle duplicates [OK]

Common Mistakes:

• Ignoring duplicates on right subtree
• Using strict greater than instead of greater or equal
• Confusing left subtree duplicates