For a binary tree to be a binary search tree (BST), the data of all the nodes in the left sub-tree of the root node should be less than or equals to the data of the root. The data of all the nodes in the right subtree of the root node should be greater than the data of the root. This example shows how to find min & max value of a binary search tree.
Here is an example picture of binary search tree (BST):
BtsNode:
|
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 |
package com.java2novice.ds; public class BstNode { private BstNode left; private BstNode right; private Integer data; public BstNode(Integer data) { this.data = data; } public BstNode getLeft() { return left; } public void setLeft(BstNode left) { this.left = left; } public BstNode getRight() { return right; } public void setRight(BstNode right) { this.right = right; } public Integer getData() { return data; } } |
BinarySearchTreeImpl:
|
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 |
package com.java2novice.ds; public class BinarySearchTreeImpl { private BstNode root; public boolean isEmpty() { return (this.root == null); } public void insert(Integer data) { System.out.print("[input: "+data+"]"); if(root == null) { this.root = new BstNode(data); System.out.println(" -> inserted: "+data); return; } insertNode(this.root, data); System.out.print(" -> inserted: "+data); System.out.println(); } private BstNode insertNode(BstNode root, Integer data) { BstNode tmpNode = null; System.out.print(" ->"+root.getData()); if(root.getData() >= data) { System.out.print(" [L]"); if(root.getLeft() == null) { root.setLeft(new BstNode(data)); return root.getLeft(); } else { tmpNode = root.getLeft(); } } else { System.out.print(" [R]"); if(root.getRight() == null) { root.setRight(new BstNode(data)); return root.getRight(); } else { tmpNode = root.getRight(); } } return insertNode(tmpNode, data); } public Integer findMinValue() { return minValue(this.root); } public Integer findMaxValue() { return maxValue(this.root); } private Integer minValue(BstNode node) { if(node.getLeft() != null) { return minValue(node.getLeft()); } return node.getData(); } private Integer maxValue(BstNode node) { if(node.getRight() != null) { return maxValue(node.getRight()); } return node.getData(); } public static void main(String a[]) { BinarySearchTreeImpl bst = new BinarySearchTreeImpl(); bst.insert(10); bst.insert(20); bst.insert(21); bst.insert(8); bst.insert(6); bst.insert(16); bst.insert(23); bst.insert(2); System.out.println("-------------------"); System.out.println("Min value: "+bst.findMinValue()); System.out.println("Max value: "+bst.findMaxValue()); } } |
Output:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
[input: 10] -> inserted: 10 [input: 20] ->10 [R] -> inserted: 20 [input: 21] ->10 [R] ->20 [R] -> inserted: 21 [input: 8] ->10 [L] -> inserted: 8 [input: 6] ->10 [L] ->8 [L] -> inserted: 6 [input: 16] ->10 [R] ->20 [L] -> inserted: 16 [input: 23] ->10 [R] ->20 [R] ->21 [R] -> inserted: 23 [input: 2] ->10 [L] ->8 [L] ->6 [L] -> inserted: 2 ------------------- Min value: 2 Max value: 23 |
