Find minimum/maximum value in binary search tree (BST) using java (DFS/example)

• Given a binary search tree (BST), find minimum & maximum element in a BST
• Traverse the binary search tree using depth first search (DFS) recursive algorithm .
• Properties of binary search trees are:
  • Left child node is less than its parent node.
  • Right child node is greater than its parent node.
  • The properties should hold good for all subtrees in a BST.
• We will demonstrate couples of examples to find min and max node in a BST.
• We have discussed about find min & max element in a binary tree.
• We will use the properties of BST to find minimum & maximum value.
  • We are not required to traverse the whole binary search tree.

What is minimum element in BST ?

• Leftmost child in a BST, is the minimum element.
• Traverse left nodes of binary search tree to find minimum element.
  • No need to traverse the right nodes of BST.

What is maximum element in BST?

• The right most child of BST, is the maximum element.
• Traverse right nodes of binary search tree to find maximum element.
  • No need to traverse the left  nodes of binary search tree.

Example 1: find min & max value in a BST (Fig 1).

• Left most child i.e. Node B (50) is minimum element in a BST.
• Right most child i.e. Node C (150) is maximum element in a BST.

Example 2: find min & max value in a BST (Fig 2).

• Minimum value of BST is 10
• Maximum value of BST is 170.

Algorithm to find minimum element in a binary search tree

• Start from root node
• Go to left child
  •  Keep on iterating  (or recursively) till, we get left child as null
  • We found the minimum value in binary search tree.

Program to find minimum element in a BST

public static int min(Node root) {
  if(null == root) {
   System.out.println("Tree is empty");
   return -1;
  }
  //we found the min value
  if(root.left == null) {
   return root.data;
  }
  return min(root.left);
 }

Algorithm to find maximum element in a binary search tree

• Start from root node
• Go to right child
  •  Keep iterating (or recursively) till we found right child as null
  • We found the maximum value in binary search tree

Program to find maximum value in BST.

public static int max(Node root) {
  if(null == root) {
   System.out.println("Tree is empty");
   return -1;
  }
  //we found the max value
  if(root.right == null) {
   return root.data;
  }
  return max(root.right);
 }
}

Complete program to find minimum & maximum element in a BST

1.) MinAndMaxInBST class:

• MinAndMaxInBST class is responsible for finding minimum and maximum element in BST.

  

package org.learn.Question;

public class MinAndMaxInBST {
 public static int min(Node root) {
  if(null == root) {
   System.out.println("Tree is empty");
   return -1;
  }
  //we found the min value
  if(root.left == null) {
   return root.data;
  }
  return min(root.left);
 }
 
 public static int max(Node root) {
  if(null == root) {
   System.out.println("Tree is empty");
   return -1;
  }
  //we found the max value
  if(root.right == null) {
   return root.data;
  }
  return max(root.right);
 }
}

2.) Node Class:

• Node class is representing the nodes of a BST.

package org.learn.Question;

public class Node {
 public int data;
 public Node left;
 public Node right;

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

 public Node() {
  this.left = null;
  this.right = null;
 }
 
 public static Node createNode(int number) {
  return new Node(number);
 }
}

3.) App Class:

• We are creating a binary tree in a main method.
• We are calling method of MinAndMaxInBST  class, to find minimum/maximum element in a BST.

package org.learn.Client;

import org.learn.Question.MinAndMaxInBST;
import org.learn.Question.Node;

public class App {
 public static void main(String[] args) {
  // root level 0
  Node A = Node.createNode(100);
  // Level 1
  Node B = Node.createNode(50);
  Node C = Node.createNode(150);
  // Level 2
  Node D = Node.createNode(25);
  Node E = Node.createNode(80);
  Node F = Node.createNode(125);
  Node G = Node.createNode(170);

  // Level 3
  Node H = Node.createNode(10);
  Node I = Node.createNode(30);
  Node J = Node.createNode(60);
  Node K = Node.createNode(90);
  Node L = Node.createNode(110);
  Node M = Node.createNode(140);

  // connect Level 0 and 1
  A.left  = B;
  A.right = C;
  
  // connect level 1 and level 2
  B.left  = D;
  B.right = E;
  C.left  = F;
  C.right = G;

  // connect level 1 and level 2
  D.left  = H;
  D.right = I;
  E.left  = J;
  E.right = K;
  F.left  = L;
  F.right = M;
  
  System.out.println("Min value in BST is : " + MinAndMaxInBST.min(A));
  System.out.println("Max value in BST is : " + MinAndMaxInBST.max(A));
 }
}

Output – min & max value in a BST

Min value in BST is : 10
Max value in BST is : 170

Download Code – Min & Max Element in BST (Recursive)