In this post, we will learn How to write a java program to find the node with minimum and maximum values in a Binary Search Tree?
If we want to find the node with minimum and maximum values in a binary search tree (BST) that is a very simple operation because of the way binary search tree (BST) is structured.
As we know that in Binary search tree, for each node the node’s left child must have a value less than its parent node value and the node’s right child must have a value greater than or equal to its parent node value. If we consider the root node of the binary search tree the left subtree must have nodes with values less than the root node value and the right subtree must have nodes with values greater than the root node value.
So, the Logic to find the node with the minimum value in a Binary search tree are as follows-
- We have to start from the root node go to its left child.
- Afterward, we have to keep traverse to the left children of each node until a node with no left child is reached and that node is a node with minimum value.
We have similar Logic to find the node with maximum value in a Binary search tree are as follows-
- We have to start from the root node and go to its right child.
- Afterward, we have to keep traverse to the right children of each node until a node with no right child is reached and that node is a node with maximum value.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
/** * Method to find node with minimum value * @param node * @return Node with Min value in BST */ public Node<E> findMinNodeInBST(Node<E> node){ if(node.left != null){ return findMinNodeInBST(node.left); } return node; } /** * Method to find node with maximum value * @param node * @return Node with Max value in BST */ public Node<E> findMaxNodeInBST(Node<E> node){ if(node.right != null){ return findMaxNodeInBST(node.right); } return node; } |
Complete Souce code:
BinaryTree.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
package com.kkjavatutorials.tree; public class BinaryTree<E extends Comparable<? super E>> { //Root of Binary Tree private Node<E> root; /** * This internal class represents Node in Binary tree * @author KK JavaTutorials */ public static class Node<T> { //Data hold by Binary Tree Node public T data; //Left pointer/reference public Node<T> left; //Right pointer/reference public Node<T> right; public Node(T data) { this.data = data; } } /** * Recursive method for preOrder Processing * in BST * @param root Node */ public void preOrder(Node<E> root) { if(root != null) { System.out.print(root.data+" "); preOrder(root.left); preOrder(root.right); } } /** * Insert operation in binary search tree * @param data to insert */ public void insert(E data) { root = insert(root, data); } private static <T extends Comparable<? super T>> Node<T> insert(Node<T> node, T data) { if (node == null) { node = new Node<T>(data); } else if (data.compareTo(node.data) < 0) { node.left = insert(node.left, data); } else if (data.compareTo(node.data) > 0) { node.right = insert(node.right, data); } return node; } /** * Method to find node with minimum value * @param node * @return Node with Min value in BST */ public Node<E> findMinNodeInBST(Node<E> node){ if(node.left != null){ return findMinNodeInBST(node.left); } return node; } /** * Method to find node with maximum value * @param node * @return Node with Max value in BST */ public Node<E> findMaxNodeInBST(Node<E> node){ if(node.right != null){ return findMaxNodeInBST(node.right); } return node; } public Node<E> getRoot() { return root; } } |
ClientTest.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
package com.kkjavatutorials.client; import com.kkjavatutorials.tree.BinaryTree; import com.kkjavatutorials.tree.BinaryTree.Node; /** * Client Program to Find the node with minimum * and maximum values in a Binary Search Tree(BST) * @author KK JavaTutorials */ public class ClientTest { public static void main(String[] args) { //Create an Instance of BinaryTree BinaryTree<Integer> binaryTree = new BinaryTree<>(); binaryTree.insert(10); binaryTree.insert(15); binaryTree.insert(5); binaryTree.insert(40); binaryTree.insert(80); binaryTree.insert(50); //Get Root Node of tree Which holds entire tree Node<Integer> root = binaryTree.getRoot(); System.out.println("Original Binary Search Tree in preOrder processing.."); //Call for preOrder processing binaryTree.preOrder(root); /*Now call Methods findMaxNodeInBST & findMinNodeInBST to get Max and Min Nodes in BST*/ Node<Integer> findMaxNodeInBST = binaryTree.findMaxNodeInBST(root); Node<Integer> findMinNodeInBST = binaryTree.findMinNodeInBST(root); System.out.println(); System.out.println("Max Element in Binary Seach Tree is:"+findMaxNodeInBST.data); System.out.println("Min Element in Binary Seach Tree is:"+findMinNodeInBST.data); } } |
The output of This Program:
Original Binary Search Tree in preOrder processing..
10 5 15 40 80 50
Max Element in Binary Seach Tree is:80
Min Element in Binary Seach Tree is:5
You May Also Like:
Introduction to Tree Data Structure
Introduction to Binary Tree
Structure of Binary Trees
Operations and use of Binary Trees
Insert operation in a binary search tree
Delete operation in a binary search tree
Search operation in a binary search tree
Binary Tree Traversals
PreOrder traversal of binary tree implementation in Java
InOrder traversal of binary tree implementation in Java
PostOrder traversal of binary tree implementation in Java
That’s all about Find the node with minimum and maximum values in a Binary Search Tree?
If you have any feedback or suggestion please feel free to drop in below comment box.