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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
package edu.caltech.cs2.datastructures;
import edu.caltech.cs2.interfaces.ICollection;
import edu.caltech.cs2.interfaces.IQueue;
import edu.caltech.cs2.interfaces.IDictionary;
import java.util.Iterator;
public class BSTDictionary<K extends Comparable<? super K>, V>
implements IDictionary<K, V> {
private BSTNode<K, V> root;
private int size;
/**
* Class representing an individual node in the Binary Search Tree
*/
private static class BSTNode<K, V> {
public final K key;
public V value;
public BSTNode<K, V> left;
public BSTNode<K, V> right;
/**
* Constructor initializes this node's key, value, and children
*/
public BSTNode(K key, V value) {
this.key = key;
this.value = value;
this.left = null;
this.right = null;
}
public BSTNode(BSTNode<K, V> o) {
this.key = o.key;
this.value = o.value;
this.left = o.left;
this.right = o.right;
}
public boolean isLeaf() {
return this.left == null && this.right == null;
}
public boolean hasBothChildren() {
return this.left != null && this.right != null;
}
}
/**
* Initializes an empty Binary Search Tree
*/
public BSTDictionary() {
this.root = null;
this.size = 0;
}
@Override
public V get(K key) {
return null;
}
@Override
public V remove(K key) {
return null;
}
@Override
public V put(K key, V value) {
return null;
}
@Override
public boolean containsKey(K key) {
return false;
}
@Override
public boolean containsValue(V value) {
return false;
}
/**
* @return number of key/value pairs in the BST
*/
@Override
public int size() {
return this.size;
}
@Override
public ICollection<K> keys() {
return null;
}
@Override
public ICollection<V> values() {
return null;
}
/**
* Implementation of an iterator over the BST
*/
@Override
public Iterator<K> iterator() {
return keys().iterator();
}
@Override
public String toString() {
if (this.root == null) {
return "{}";
}
StringBuilder contents = new StringBuilder();
IQueue<BSTNode<K, V>> nodes = new ArrayDeque<>();
BSTNode<K, V> current = this.root;
while (current != null) {
contents.append(current.key + ": " + current.value + ", ");
if (current.left != null) {
nodes.enqueue(current.left);
}
if (current.right != null) {
nodes.enqueue(current.right);
}
current = nodes.dequeue();
}
return "{" + contents.toString().substring(0, contents.length() - 2) + "}";
}
}