BST Find Maximum Element in DSA Java - 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 right until no right child exists. The last node visited is the maximum.

Execution Sample

DSA Java

Node findMax(Node root) {
  Node current = root;
  while (current.right != null) {
    current = current.right;
  }
  return current;
}

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

Execution Table

Step	Operation	Current Node	Right Child Exists?	Action	Visual State
1	Start at root	50	Yes	Move to right child	50 -> 70 -> 90 -> null
2	At node 70	70	Yes	Move to right child	50 -> 70 -> 90 -> null
3	At node 90	90	No	Stop, max found	50 -> 70 -> 90 -> null
4	Return max	90	N/A	Return node 90	50 -> 70 -> 90 -> null

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

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
current	50 (root)	70	90	90	90

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. So moving right leads to larger values. See execution_table steps 1 and 2 where current moves right.

What if the root has no right child?

If root.right is null at start, the root itself is the maximum. This is shown in execution_table step 3 where no right child means stop.

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

Stopping at current.right == null means current is the last node on the right path, which is the max. If we stopped at current == null, we would go past the max node. See step 3.

Visual Quiz - 3 Questions

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

A 50

B 70

C 90

D null

💡 Hint

Check the 'Current Node' column in execution_table row for step 2.

At which step does the algorithm find that there is no right child?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at the 'Right Child Exists?' column in execution_table.

If the root node had no right child, what would be the maximum element?

A The root node itself

B The left child of root

C Null

D The right child of root

💡 Hint

Refer to key_moments explanation about root with no right child.

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
- Max is rightmost node in BST

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 and repeat. Continue moving right until you reach a node with no right child. That node is the maximum element in the BST. This works because in BSTs, right children always have greater values than their parents. The code uses a loop to move right until current.right is null, then returns the current node as max.

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 are smaller and right child nodes are larger than the parent node.

2. Step 2: Locate maximum element

   The maximum element is the rightmost node because it has no larger right child.

3. Final Answer:

   At the rightmost node -> Option D

4. Quick Check:

   Maximum = rightmost node [OK]

Hint: Maximum is always the farthest right node in BST [OK]

Common Mistakes:

• Confusing maximum with root node
• Thinking maximum is at leftmost node
• Assuming maximum can be any leaf

2. Which of the following Java method signatures correctly finds the maximum element in a BST node class named Node?

easy

A. public int findMax(Node root) { while(root.right != null) root = root.right; return root.data; }

B. public int findMax(Node root) { return root.left.data; }

C. public int findMax(Node root) { if(root == null) return 0; return root.data; }

D. public int findMax(Node root) { while(root.left != null) root = root.left; return root.data; }

Solution

1. Step 1: Check traversal direction for maximum

   Maximum is found by moving right until no right child exists.

2. Step 2: Verify method logic

   public int findMax(Node root) { while(root.right != null) root = root.right; return root.data; } correctly loops while root.right is not null, then returns root.data.

3. Final Answer:

   public int findMax(Node root) { while(root.right != null) root = root.right; return root.data; } -> Option A

4. Quick Check:

   Traverse right to find max [OK]

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

Common Mistakes:

• Looping left child instead of right
• Returning root data without traversal
• Not checking for null root

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; }
}

public class BST {
  public static int findMax(Node root) {
    while(root.right != null) root = root.right;
    return root.data;
  }

  public static void main(String[] args) {
    Node root = new Node(10);
    root.left = new Node(5);
    root.right = new Node(20);
    root.right.right = new Node(30);
    System.out.println(findMax(root));
  }
}

medium

A. 20

B. 30

C. 10

D. 5

Solution

1. Step 1: Trace the BST structure

   Root=10, left=5, right=20, right.right=30. Maximum is rightmost node 30.

2. Step 2: Follow findMax method

   Loop moves from 10 to 20 to 30, then stops as 30.right is null, returns 30.

3. Final Answer:

   30 -> Option B

4. Quick Check:

   Rightmost node data = 30 [OK]

Hint: Follow right children to last node for max [OK]

Common Mistakes:

• Returning root data without traversal
• Confusing left and right children
• Ignoring right.right node

4. Identify the error in the following Java method to find the maximum element in a BST and select the corrected version.

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

medium

A. Add recursive call instead of while loop

B. Return 0 instead of -1 when root is null

C. Change root.left to root.right in while loop

D. No error, code is correct

Solution

1. Step 1: Analyze traversal direction

   Maximum is found by moving right, but code moves left incorrectly.

2. Step 2: Correct the while loop

   Change while(root.left != null) to while(root.right != null) to find max correctly.

3. Final Answer:

   Change root.left to root.right in while loop -> Option C

4. Quick Check:

   Traverse right child for max [OK]

Hint: Max is rightmost, so loop on right child [OK]

Common Mistakes:

• Looping left child instead of right
• Returning wrong default value
• Thinking recursion is mandatory

5. Given a BST where some nodes have duplicate values, which approach correctly finds the maximum element considering duplicates?

public int findMaxWithDuplicates(Node root) {
  if(root == null) return Integer.MIN_VALUE;
  int maxVal = root.data;
  while(root.right != null) {
    root = root.right;
    if(root.data > maxVal) maxVal = root.data;
  }
  return maxVal;
}

What is the output of findMaxWithDuplicates for this BST? Root=15, root.left=10, root.right=20, root.right.right=20, root.right.right.right=25

hard

A. 25

B. 20

C. 15

D. Duplicate values cause error

Solution

1. Step 1: Understand BST with duplicates

   Duplicates can appear on right subtree; max is still rightmost largest value.

2. Step 2: Trace method execution

   Traverse right: 15 -> 20 -> 20 -> 25; maxVal updates to 25 at last node.

3. Final Answer:

   25 -> Option A

4. Quick Check:

   Rightmost node data = 25 [OK]

Hint: Rightmost node holds max even with duplicates [OK]

Common Mistakes:

• Stopping at first duplicate max value
• Assuming duplicates cause errors
• Ignoring rightmost traversal