Find Minimum and Maximum Value Nodes in Binary Search Tree - Java Program

If we have to find the node with minimum value and node with maximum value in a binary search tree that is a simple operation because of the way binary search tree is structured.

As we know in Binary search tree, for each node the node’s left child must have a value less than its parent node and the node’s right child must have a value greater than or equal to its parent. If we consider the root node of the binary search tree the left subtree must have nodes with values less than the root node and the right subtree must have nodes with values greater than the root node.

So the steps for finding the node with minimum value in a Binary search tree are as follows-

1. Starting from the root node go to its left child.
2. Keep traversing the left children of each node until a node with no left child is reached. That node is a node with minimum value.

Same way steps for finding the node with maximum value in a Binary search tree are as follows-

1. Starting from the root node go to its right child.
2. Keep traversing the right children of each node until a node with no right child is reached. That node is a node with maximum value.

Following image shows the traversal of nodes in a BST for minimum and maximum nodes.

Find nodes with min and max values in a BST – Java Program

public class MinAndMaxBST {
  // first node
  private Node root;
  MinAndMaxBST(){
    root = null;
  }
  // Class representing tree nodes
  static class Node{
    int value;
    Node left;
    Node right;
    Node(int value){
      this.value = value;
      left = null;
      right = null;        
    }
    public void displayData(){
      System.out.print(value + " ");
    }
  }
    
  public void insert(int i){
    root = insert(root, i);
  }
    
  //Inserting node - recursive method
  public Node insert(Node node, int value){
    if(node == null){
      return new Node(value);
    }
    // Move to the left if passed value is 
    // less than the current node
    if(value < node.value){
      node.left = insert(node.left, value);
    }
    // Move to the right if passed value is 
    // greater than the current node
    else if(value > node.value){
      node.right = insert(node.right, value);
    }
    return node;
  }
    
  // For traversing in order
  public void inOrder(Node node){
    if(node != null){
      inOrder(node.left);
      node.displayData();
      inOrder(node.right);
    }
  }
  // Finding node with min value
  public Node findMinimum(Node node){
    if(node.left != null){
      return findMinimum(node.left);
    }
    return node;
  }
  // Finding node with max value    
  public Node findMaximum(Node node){
    if(node.right != null){
      return findMaximum(node.right);
    }
    return node;
  }
    
  public static void main(String[] args) {
    MinAndMaxBST bst = new MinAndMaxBST();
    bst.insert(50);
    bst.insert(70);        
    bst.insert(30);
    bst.insert(15);
    bst.insert(35);
    bst.insert(7);
    bst.insert(22);
    System.out.println("Inorder traversal of binary tree");
    bst.inOrder(bst.root);
    System.out.println();
    Node minNode = bst.findMinimum(bst.root);
    Node maxNode = bst.findMaximum(bst.root);
    System.out.println("Minimum node value- " + minNode.value);
    System.out.println("Maximum node value- " + maxNode.value);
  }
}

Output

Inorder traversal of binary tree
7 15 22 30 35 50 70 
Minimum node value- 7
Maximum node value- 70

That's all for this topic Find Minimum and Maximum Value Nodes in Binary Search Tree - Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

---

Related Topics

1. Java Program to Delete a Node From Binary Search Tree (BST)
2. Linked List Implementation Java Program
3. Linear Search (Sequential Search) Java Program
4. Convert Numbers to Words Java Program
5. Count Number of Times Each Character Appears in a String Java Program

You may also like-

1. Reading File in Java Using BufferedReader
2. Java Lambda Expression Callable Example
3. How to Find Common Elements Between Two Arrays Java Program
4. How to Compile Java Program at Runtime
5. Reflection in Java - Getting Class Information
6. Thread States (Thread Life Cycle) in Java Multi-Threading
7. Try-With-Resources in Java With Examples
8. Apache Avro Format in Hadoop