BST Find Maximum Element in DSA Java - Build from Scratch

BST Find Maximum Element

📖 Scenario: You are working with a Binary Search Tree (BST) that stores numbers. You want to find the largest number stored in this tree.Think of the BST like a family tree where each person has children with bigger or smaller ages. The biggest age is what you want to find.

🎯 Goal: Build a simple BST with given numbers and write code to find the maximum number in the BST.

📋 What You'll Learn

Create a BST node class with integer data and left/right child references

Insert given numbers into the BST in the given order

Write a method to find the maximum element in the BST

Print the maximum element found

💡 Why This Matters

🌍 Real World

BSTs are used in databases and file systems to quickly find the largest or smallest values.

💼 Career

Understanding BST operations like finding maximum is important for software engineering roles involving data structures and algorithms.

1

Create BST Node and Insert Numbers

Create a class called Node with an integer data, and two Node references called left and right. Then create a class called BST with a Node variable called root. Write a method insert that takes an integer and inserts it into the BST following BST rules. Insert these numbers in order: 50, 30, 70, 20, 40, 60, 80 into the BST starting from root.

DSA Java

// Create Node class and BST class with insert method
// Insert 50, 30, 70, 20, 40, 60, 80 into BST
// Your code here

Hint

Remember, in a BST, smaller numbers go to the left child, bigger numbers go to the right child.

2

Add Method to Find Maximum Element

In the BST class, add a method called findMax that returns an integer. This method should find the maximum element in the BST by starting at root and moving to the right child until there is no more right child.

DSA Java

class Node {
    int data;
    Node left, right;

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

class BST {
    Node root;

    BST() {
        root = null;
    }

    void insert(int data) {
        root = insertRec(root, data);
    }

    Node insertRec(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }
        if (data  root.data) {
            root.right = insertRec(root.right, data);
        }
        return root;
    }

    int findMax() {
        // Your code here
    }

    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(50);
        tree.insert(30);
        tree.insert(70);
        tree.insert(20);
        tree.insert(40);
        tree.insert(60);
        tree.insert(80);
    }
}

Hint

In a BST, the maximum value is always the rightmost node.

3

Call findMax Method in main

In the main method of the BST class, call the findMax method on the tree object and store the result in an integer variable called maxValue.

DSA Java

class Node {
    int data;
    Node left, right;

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

class BST {
    Node root;

    BST() {
        root = null;
    }

    void insert(int data) {
        root = insertRec(root, data);
    }

    Node insertRec(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }
        if (data  root.data) {
            root.right = insertRec(root.right, data);
        }
        return root;
    }

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

    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(50);
        tree.insert(30);
        tree.insert(70);
        tree.insert(20);
        tree.insert(40);
        tree.insert(60);
        tree.insert(80);
        // Your code here
    }
}

Hint

Call the findMax method on the tree object and save the result in maxValue.

4

Print the Maximum Element

In the main method, print the value of maxValue using System.out.println.

DSA Java

class Node {
    int data;
    Node left, right;

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

class BST {
    Node root;

    BST() {
        root = null;
    }

    void insert(int data) {
        root = insertRec(root, data);
    }

    Node insertRec(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }
        if (data  root.data) {
            root.right = insertRec(root.right, data);
        }
        return root;
    }

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

    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(50);
        tree.insert(30);
        tree.insert(70);
        tree.insert(20);
        tree.insert(40);
        tree.insert(60);
        tree.insert(80);
        int maxValue = tree.findMax();
        // Print maxValue
        // Your code here
    }
}

Hint

Use System.out.println(maxValue); to print the maximum 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 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