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)