BST Find Maximum Element in DSA Javascript - Execution Trace

Concept Flow - BST Find Maximum Element

Start at root node

↓

Check if right child exists?

No→Current node is max

Yes↓

Move to right child

↩Back to check right child

Start at the root and keep moving to the right child until no right child exists; that node is the maximum.

Execution Sample

DSA Javascript

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

This code finds the maximum value in a BST by moving right until no right child exists.

Execution Table

Step	Operation	Current Node Value	Right Child Exists?	Pointer Changes	Visual State
1	Start at root	15	Yes	current = root (15)	15 / \ 10 20 / \ 17 25
2	Move right	20	Yes	current = current.right (20)	15 / \ 10 20 / \ 17 25
3	Move right	25	No	current = current.right (25)	15 / \ 10 20 / \ 17 25
4	No right child	25	No	Stop	15 / \ 10 20 / \ 17 25

💡 No right child at node 25, so 25 is the maximum element.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
current.value	15	15	20	25	25

Key Moments - 3 Insights

Why do we keep moving to the right child to find the maximum?

In a BST, all right children have values greater than their parent. The execution_table rows 1 to 3 show moving right to find larger values until no right child exists.

What if the tree has only one node?

If the root has no right child (like step 1 with no right child), the root itself is the maximum, as shown in the exit condition at step 4.

Why do we stop when current.right is null, not when current is null?

Stopping when current.right is null means current is the largest node. If we moved until current is null, we would go past the largest node, losing the reference. See step 4 in execution_table.

Visual Quiz - 3 Questions

Look at the execution_table, what is the value of current after step 2?

A 20

B 15

C 25

D 17

💡 Hint

Check the 'Current Node Value' column at step 2 in execution_table.

At which step does the algorithm stop because there is no right child?

A Step 3

B Step 2

C Step 4

D Step 1

💡 Hint

Look for the step where 'Right Child Exists?' is 'No' and operation is 'No right child' in execution_table.

If the node with value 25 had a right child 30, what would be the current node value after step 3?

A 25

B 30

C 20

D 17

💡 Hint

If right child exists, current moves right as per execution_table steps 2 and 3.

Concept Snapshot

BST Find Maximum Element:
- Start at root node
- While right child exists, move right
- When no right child, current node is max
- Return current node's value
- Works because right subtree has larger values

Full Transcript

To find the maximum element in a Binary Search Tree (BST), start at the root node. Check if the current node has a right child. If yes, move to that right child. Repeat this until the current node has no right child. The node without a right child is the maximum element. This works because in BSTs, right children always have greater values than their parents. The code uses a loop to move right until no right child is found, then returns that node's value.

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