BST Find Maximum Element in DSA Java

Mental Model

In a Binary Search Tree, the biggest number is always the rightmost node. We just keep going right until we can't go further.

Analogy: Imagine a family tree where older generations are on the left and younger generations on the right. The youngest person is the one farthest to the right.

      10
     /  \
    5    15
          \
           20
            \
             25
             ↑ (start here)

Dry Run Walkthrough

Input: BST: 10 -> 5 (left), 15 (right) -> 20 (right of 15) -> 25 (right of 20). Find max element.

Goal: Find the largest value in the BST by moving right until no more right child exists.

Step 1: Start at root node 10

10 -> [curr->15] -> 20 -> 25 -> null

Why: We start at the root and move right because bigger values are on the right.

Step 2: Move curr to right child 15

10 -> 15 -> [curr->20] -> 25 -> null

Why: 15 is bigger than 10, so we keep moving right.

Step 3: Move curr to right child 20

10 -> 15 -> 20 -> [curr->25] -> null

Why: 20 is bigger than 15, continue moving right.

Step 4: Move curr to right child 25

10 -> 15 -> 20 -> 25 -> [curr->null]

Why: 25 is bigger than 20, move right again.

Step 5: curr.right is null, stop and return curr.value 25

10 -> 15 -> 20 -> 25 -> null

Why: No more right child means 25 is the maximum.

Result:

10 -> 15 -> 20 -> 25 -> null
Maximum element found: 25

Annotated Code

DSA Java

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

public class BSTFindMax {
    // Find max value in BST by going right until no right child
    public static int findMax(Node root) {
        if (root == null) {
            throw new IllegalArgumentException("BST is empty");
        }
        Node curr = root;
        while (curr.right != null) {
            curr = curr.right; // move right to find bigger value
        }
        return curr.value; // rightmost node value is max
    }

    public static void main(String[] args) {
        Node root = new Node(10);
        root.left = new Node(5);
        root.right = new Node(15);
        root.right.right = new Node(20);
        root.right.right.right = new Node(25);

        int max = findMax(root);
        System.out.println("10 -> 15 -> 20 -> 25 -> null");
        System.out.println("Maximum element found: " + max);
    }
}

if (root == null) { throw new IllegalArgumentException("BST is empty"); }

handle empty tree edge case

Node curr = root;

start from root node

while (curr.right != null) { curr = curr.right; }

keep moving right to find the largest value

return curr.value;

return the rightmost node's value as max

Output

10 -> 15 -> 20 -> 25 -> null

Maximum element found: 25

Complexity Analysis

Time: O(h) because we only traverse down the right children where h is the height of the tree

Space: O(1) because we use only a few variables and no extra space proportional to input size

vs Alternative: Compared to traversing the whole tree (O(n)), this is faster because BST property lets us go directly right.

Edge Cases

Empty BST

Throws an exception because there is no maximum in an empty tree

DSA Java

if (root == null) { throw new IllegalArgumentException("BST is empty"); }

BST with only one node

Returns the single node's value as maximum

DSA Java

while (curr.right != null) { curr = curr.right; }

BST where all nodes are left children (no right children)

Returns the root value as maximum since no right child exists

DSA Java

while (curr.right != null) { curr = curr.right; }

When to Use This Pattern

When you need the largest value in a BST, look for the rightmost node because BSTs keep bigger values on the right.

Common Mistakes

Mistake: Trying to check left children or traversing the whole tree to find max
Fix: Only move right until no right child exists to find the maximum efficiently

Summary

Finds the largest value in a BST by moving right until no more right child exists.

Use when you want the maximum element in a BST quickly without searching the entire tree.

The key insight is that the maximum is always the rightmost node in a BST.

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