-
Notifications
You must be signed in to change notification settings - Fork 1
/
countRange.java
115 lines (102 loc) · 3.09 KB
/
countRange.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
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
public class countRange {
public static class BinarySearchTree<E extends Comparable<? super E>>{
//////////////////////////////////////////////////
/*
* This static nested class encapsulates a node in the tree.
*/
private class Node<E>{
private E data;
private Node<E> parent;
private Node<E> leftSubTree;
private Node<E> rightSubTree;
private int size;
public Node(E data, Node<E> leftSubTree, Node<E> rightSubTree){
this.data = data;
this.leftSubTree = leftSubTree;
this.rightSubTree = rightSubTree;
this.size = 1;
}
}
////////////////////////////////////////////////////
// Ensure the parameterized type can be sorted.//
private Node<E> root;
/**
* Initializes an empty binary search tree.
*/
public BinarySearchTree(){
root = null;
}
/**
* Adds the passed value to the tree.
* @param value the value to add to the tree
*/
public void add(E value){
root = addNode(root, value);
}
// Solves 'add' recursively.//
private Node<E> addNode(Node<E> root, E value){
Node<E> result = null;
if (root == null){ // Base case, add node here.//
result = new Node<E>(value, null, null);
}
else if (root.data.compareTo(value) > 0){ // Recursive case, go left.//
root.leftSubTree = addNode(root.leftSubTree, value);
root.size = root.size+1;
result = root;
}
else { // Recursive case, go right.//
root.rightSubTree = addNode(root.rightSubTree, value);
root.size = root.size+1;
result = root;
}
return result;
}
public int countRange(Node<E> root, int k1, int k2){
// Base case
if (root == null) {
return 0;
}
// If current node is in countRange, then include it in count and
// recur for left and right children of it
if ((int)root.data <= k2 && (int)root.data >= k1){
return countRange(root.leftSubTree,k1, k2) + countRange(root.rightSubTree,k1, k2) +1;
}
// If current node is smaller than k1, then recur for right
else if ((int)root.data < k1){
return countRange(root.rightSubTree, k1, k2);
}
// else go left
else {
return countRange(root.leftSubTree, k1, k2);
}
}
public String toString(){
StringBuffer sb = new StringBuffer();
infixPrint(root, 0, sb);
return sb.toString().trim();
}
private void infixPrint(Node<E> root, int size ,StringBuffer sb){
if (root != null){
sb.append("["+root.data + ", " + root.size + "],");
infixPrint(root.leftSubTree, root.size, sb);
infixPrint(root.rightSubTree, root.size, sb);
}
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
bst.add(44);
bst.add(17);
bst.add(32);
bst.add(78);
bst.add(50);
bst.add(88);
bst.add(48);
bst.add(62);
System.out.println("The Tree with size of each Node");
System.out.println(bst.toString());
System.out.println("Range between:- 32, 88");
System.out.println(bst.countRange(bst.root,32,88));
}
}