Introduction
Hey there, welcome back to “Art of Coding”! If you’ve been following our journey through the world of Binary Search Trees (BSTs), you’re in for a treat. Today, we’re rolling up our sleeves to tackle another common challenge: finding the minimum and maximum elements in a BST, using our favorite language, Java.
We’re going to break it down for you, step by step, so you can not only understand but also apply these concepts in your coding adventures.
So, grab a cup of your favorite coffee, and let’s get started!
Understanding the BST Structure for Min/Max Values
Before we jump into the coding specifics, let’s quickly revisit the structure of a Binary Search Tree. A BST is a rooted binary tree whose each node has up to two children, and they’re arranged according to one simple rule: for any given node, all values in its left subtree are smaller, and all values in its right subtree are larger.
Why does this matter for finding the minimum and maximum values? Well, thanks to this rule, the minimum value in a BST is the leftmost node, and the maximum value is the rightmost node.
Take a look at the image we’ve included here. You’ll notice the node with the value of 3 is colored differently. That’s because it’s our leftmost node—our minimum value. On the other side, the node with the value of 18 stands out, rightly taking its place as the rightmost node—our maximum value.
Java Implementation: Finding Min and Max in a BST
To facilitate the process of finding the minimum and maximum values, we have two classes: Node and TreeUtil. The Node class represents each node in the tree, encapsulating the element value, as well as references to the left and right children.
Here’s a peek at the Node class:
public class Node {
private int element;
private Node left;
private Node right;
public Node(int data) {
this.element = data;
}
public void add(int newValue) {
if (newValue < this.element) {
// If newValue is less than the current node's value, go left
if (this.left == null) {
// If left child is null, create a new node and assign it
this.left = new Node(newValue);
} else {
// If left child exists, recursively call add on the left subtree
this.left.add(newValue);
}
} else {
// If newValue is greater than or equal to the current node's value, go right
if (this.right == null) {
// If right child is null, create a new node and assign it
this.right = new Node(newValue);
} else {
// If right child exists, recursively call add on the right subtree
this.right.add(newValue);
}
}
}
public int getElement() {
return element;
}
public Node getLeft() {
return left;
}
public Node getRight() {
return right;
}
}
The add method within the Node class is a perfect showcase of recursion in action. Every time you want to insert a new value, this method ensures it finds its proper place, adhering strictly to the BST ordering rules.
If you’re intrigued by the insertion process and how this method contributes to the integrity of the BST structure, you’ll definitely enjoy our in-depth look at BST insertions. Check out our previous article, BST Insertion & In-Order Traversal: A Beginner’s Guide.
With our nodes ready, we turn to the TreeUtil class, which houses our findMinimum and findMaximum methods:
public class TreeUtil {
public static int findMinimum(Node root) {
if (root == null) {
throw new IllegalArgumentException("Root is null");
}
Node current = root;
while (current.getLeft() != null) {
current = current.getLeft();
}
return current.getElement();
}
public static int findMaximum(Node root) {
if (root == null) {
throw new IllegalArgumentException("Root is null");
}
Node current = root;
while (current.getRight() != null) {
current = current.getRight();
}
return current.getElement();
}
}These methods are static, meaning you can call them without creating an instance of TreeUtil. They start at the root and traverse the tree down to the leftmost node for the minimum, and the rightmost node for the maximum, neatly exploiting the BST’s ordered properties.
Should the tree be empty, the findMinimum and findMaximum methods will throw an IllegalArgumentException, alerting you that there’s no data to work with.
Complexity Analysis of Finding Min and Max Values in a BST
In the case of our findMinimum and findMaximum methods, the operations are quite straightforward. They each involve traversing the tree from the root to the leftmost or rightmost leaf node to find the min or max value, respectively.
Now, let’s break it down:
Time Complexity:
- For
findMinimum: We traverse from the root to the leftmost node. In the worst case, this means visiting each level of the tree once. Therefore, the time complexity is O(h), where h is the height of the tree. - For
findMaximum: Similarly, we traverse to the rightmost node, which also results in a time complexity of O(h).
- For
Space Complexity:
- Both
findMinimumandfindMaximummethods use only a constant amount of extra space (to store the node references during the traversal), so the space complexity is O(1), which is excellent from a resource consumption standpoint.
- Both
It’s worth noting that the height of a BST can vary. In the best-case scenario, the tree is balanced, and the height h is log(n), where n is the number of nodes. In the worst case, the tree might be unbalanced, resembling a linked list, with a height of n. For a balanced tree, our methods would run in O(log(n)) time, which is very efficient.
Conclusion: Putting Theory into Practice
You now know how to navigate a Binary Search Tree to find the minimum and maximum values using Java. While the methods we discussed utilize iterative approaches, there’s always room for exploration and improvement. 🤔 Why not challenge yourself to reimplement these methods recursively? It’s a great exercise to deepen your understanding of BSTs and recursive algorithms.
If you’re looking for more tree-based adventures, don’t forget to check out our other articles on BSTs and tree data structures. You can find them here.
💬 if you have any thoughts, questions, or insights, or if you’ve tried writing the recursive methods, please drop a comment below. Your input only helps us improve.
Happy coding, and until next time 👨💻👩💻!
References
Cracking the Coding Interview: This book is a renowned best-seller and a personal favorite – an essential book for preparing for technical interviews!
Designing Data-Intensive Applications: ‘ is a go-to reference for creating scalable, robust, and high-performance applications!