Find minimum and maximum elements in binary search tree in java

In this post, we will see how to find minimum and maximum elements in binary search tree.

Finding minimum element:

Minimum element is nothing but leftmost node in binary search tree, so traverse left until you get leftmost element.
// Get minimum element in binary search tree
 public static TreeNode minimumElement(TreeNode root)
 {
  if(root.left==null)
   return root;
  else
  {
   return minimumElement(root.left);
  }
 }

Finding maximum element:

Maximum element is nothing but rightmost node in binary search tree, so traverse right until you get rightmost element.
// Get maximum element in binary search tree
 public static TreeNode maximumElement(TreeNode root)
 {
  if(root.right==null)
   return root;
  else
  {
   return maximumElement(root.right);
  }
 }

Complete java program:

package org.arpit.java2blog;

public class BinarySearchTreeMain {
 public static class TreeNode
 {
  int data;
  TreeNode left;
  TreeNode right;
  TreeNode(int data)
  {
   this.data=data;
  }
 }
 
 public static boolean search(TreeNode root,TreeNode nodeToBeSearched)
 {
  if(root==null)
   return false;
  if(root.data== nodeToBeSearched.data)
  {
   return true;
  }
  boolean result=false;
  if(root.data > nodeToBeSearched.data)
   result=search(root.left,nodeToBeSearched);
  else if(root.data < nodeToBeSearched.data)
   result= search(root.right,nodeToBeSearched);
  return result;
 }
 
 // Get minimum element in binary search tree
 public static TreeNode minimumElement(TreeNode root)
 {
  if(root.left==null)
   return root;
  else
  {
   return minimumElement(root.left);
  }
 }
 
 // Get maximum element in binary search tree
 public static TreeNode maximumElement(TreeNode root)
 {
  if(root.right==null)
   return root;
  else
  {
   return maximumElement(root.right);
  }
 }
 public static TreeNode insert(TreeNode root,TreeNode nodeToBeInserted)
 {
  if(root==null)
  {
   root=nodeToBeInserted;
   return root;
  }
  
  if(root.data > nodeToBeInserted.data)
  {
   if(root.left==null)
    root.left=nodeToBeInserted;
   else
    insert(root.left,nodeToBeInserted);
  }
  else if(root.data < nodeToBeInserted.data)
   if(root.right==null)
    root.right=nodeToBeInserted;
   else
    insert(root.right,nodeToBeInserted);
  return root;
 } 
 
 public static void inOrder(TreeNode root)
 {
  if(root==null)
   return;
  inOrder(root.left);
  System.out.print(root.data+" ");
  inOrder(root.right);
 }
 public static void main(String[] args)
 {
  
  // Creating a binary search tree
  TreeNode rootNode=createBinarySearchTree();
  System.out.println("Minimum element in binary search tree: "+minimumElement(rootNode).data);
  System.out.println("Maximum element in binary search tree: "+maximumElement(rootNode).data);
  
 }   
 
 
 public static TreeNode createBinarySearchTree()
 {
  TreeNode rootNode =new TreeNode(40);
  TreeNode node20=new TreeNode(20);
  TreeNode node10=new TreeNode(10);
  TreeNode node30=new TreeNode(30);
  TreeNode node60=new TreeNode(60);
  TreeNode node50=new TreeNode(50);
  TreeNode node70=new TreeNode(70);
  TreeNode node5=new TreeNode(5);
     TreeNode node55=new TreeNode(55);

  insert(null,rootNode);
  insert(rootNode,node20);
  insert(rootNode,node10);
  insert(rootNode,node30);
  insert(rootNode,node60);
  insert(rootNode,node50);
  insert(rootNode,node70);
  insert(rootNode,node5);
  insert(rootNode,node55);
  
  return rootNode;
 }

}

When you run above program, you will get below output:
Minimum element in binary search tree: 5
Maximum element in binary search tree: 70

Written by Arpit:

If you have read the post and liked it. Please connect with me on Facebook | Twitter | Google Plus

 

Java tutorial for beginners Copyright © 2012