If you want to practice data structure and algorithm programs, you can go through 100+ java coding interview questions.
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// 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.
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// 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:
|
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 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
package org.arpit.java2blog.binarysearchtree; public class BinarySearchTreeMinMaxMain { 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:
|
1 2 3 4 |
Minimum element in binary search tree: 5 Maximum element in binary search tree: 70 |
Was this post helpful?
Let us know if this post was helpful. Feedbacks are monitored on daily basis. Please do provide feedback as that\'s the only way to improve.
