BST Find Maximum Element in DSA Java - 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. For every node, all values in the left subtree are smaller, and all values in the right subtree are larger.

beginner

How do you find the maximum element in a BST?

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

beginner

Why does moving right in a BST lead to the maximum element?

Because in a BST, right children always have values greater than their parents, so the farthest right node holds the largest value.

intermediate

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

The time complexity is O(h), where h is the height of the BST. In the worst case (skewed tree), it can be O(n).

beginner

Show the Java code snippet to find the maximum element in a BST.

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

int findMax(Node root) {
  if (root == null) return Integer.MIN_VALUE;
  Node current = root;
  while (current.right != null) {
    current = current.right;
  }
  return current.data;
}

In a BST, where is the maximum element located?

A At the leftmost node

B At the rightmost node

C At the root node

D At any leaf node

The maximum element is always at the rightmost node because right children have larger values.

What is the first step to find the maximum element in a BST?

A Start at the root

B Move to the right child

C Check all nodes

D Move to the left child

You start at the root and then move right repeatedly to find the maximum.

What happens if the BST is empty when finding the maximum element?

A Return Integer.MIN_VALUE or an error

B Return the root value

C Return 0

D Return null

If the BST is empty, returning Integer.MIN_VALUE or signaling no maximum is appropriate.

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

A O(n)

B O(1)

C O(log n)

D O(n log n)

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

Which of these is the correct way to find the maximum element in a BST?

A Traverse left until no left child

B Return the root value

C Traverse both left and right subtrees fully

D Traverse right until no right child

Moving right until no right child leads to the maximum element.

Explain how to find the maximum element in a Binary Search Tree and why this method works.

Think about the BST property of right children.

Write a simple Java method to find the maximum element in a BST and describe its time complexity.

Use a while loop to traverse right children.

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