Section: Binary Search Trees
Recommended Activities
Review backtracking via binary tree traversals to allow access to all elements in a binary tree.
Work on the recursive methods in the BinarySearchTree<E>.
Use the following tree that gets hardcoded below to write out all three traversals.
To the BinarySearchTree class below, add the following methods
1. public boolean exists(E el)
2. public booleansameStructure(BinarySearchTree<E> other)
3. public int nodesAtLevel()
publicclassBinarySearchTree<E> {
privateclass TreeNode {
privateE data;
private TreeNode left;
private TreeNode right;
public TreeNode(E theData) {
data = theData;
left = null;
right = null;
}
} // end class TreeNode
TreeNode root; // The external reference
publicBinarySearchTree() {
root = null;
}
// Assume this works(linked under Code Demos from Monday's lecture)
publicbooleaninsert(E el) { /* */ }
======
@Test
publicvoid testExists() {
BinarySearchTree<String> aTree = new BinarySearchTree<String>();
assertFalse(aTree.exists("M"));
aTree.insert("M");
assertTrue(aTree.exists("M"));
assertFalse(aTree.exists("E"));
aTree.insert("E");
assertTrue(aTree.exists("E"));
aTree.insert("A");
aTree.insert("G");
aTree.insert("H");
aTree.insert("F");
assertTrue(aTree.exists("A"));
assertTrue(aTree.exists("G"));
assertTrue(aTree.exists("H"));
assertTrue(aTree.exists("F"));
}
@Test
public void testSameStructureWhenTrue() {
BinarySearchTree<Integer> a = new BinarySearchTree<Integer>();
BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
assertTrue(a.sameStructure(b));
a.insert(50);
b.insert(7);
assertTrue(a.sameStructure(b)); // both have one node
a.insert(30);
b.insert(3);
assertTrue(a.sameStructure(b)); // both roots have a left child
a.insert(70);
b.insert(9);
assertTrue(a.sameStructure(b)); // both roots have a left and right children
a.insert(99);
b.insert(99);
assertTrue(a.sameStructure(b));
a.insert(1);
b.insert(1);
assertTrue(a.sameStructure(b));
a.insert(2);
b.insert(2);
assertTrue(a.sameStructure(b));
}
@Test
public void testSameStructureWhenFalse() {
BinarySearchTree<Integer> a = new BinarySearchTree<Integer>();
BinarySearchTree<Integer> b = new BinarySearchTree<Integer>();
a.insert(50);
assertFalse(a.sameStructure(b));
b.insert(50);
b.insert(100);
assertFalse(a.sameStructure(b));
a.insert(25);
assertFalse(a.sameStructure(b));
a.insert(100);
b.insert(75);
assertFalse(a.sameStructure(b));
}
@Test
publicvoid testAtDepth() {
BinarySearchTree<String> threeLevels = new BinarySearchTree<String>();
threeLevels.insert("M");
threeLevels.insert("E");
threeLevels.insert("A");
threeLevels.insert("G");
threeLevels.insert("S");
threeLevels.insert("P");
threeLevels.insert("V");
assertEquals(1, threeLevels.nodesAtLevel(0));
assertEquals(2, threeLevels.nodesAtLevel(1));
assertEquals(4, threeLevels.nodesAtLevel(2));
assertEquals(0, threeLevels.nodesAtLevel(3));
assertEquals(0, threeLevels.nodesAtLevel(4));
}
Answers
Use the following tree that gets hardcoded below to write out all three traversals.
To the BinarySearchTree class below, add the following methods
publicbooleanexists(String search) {
return isThere(root, search);
}
privateboolean isThere(TreeNode t, String search) {
if (t == null)
returnfalse;
else {
if (t.data.equals(search))
returntrue;
else
return isThere(t.left, search) || isThere(t.right, search);
}
}
publicbooleansameStructure(BinarySearchTree<E> other) {
return sameStructure(root, other.root);
}
privateboolean sameStructure(TreeNode thisRoot, TreeNode otherRoot) {
if (thisRoot == null & otherRoot == null)
returntrue;
elseif (thisRoot != null & otherRoot == null || thisRoot == null
& otherRoot != null)
returnfalse;
else
return sameStructure(thisRoot.left, otherRoot.left)
& sameStructure(thisRoot.right, otherRoot.right);
}
publicintnodesAtLevel(int level) {
return atDepth(root, level);
}
privateint atDepth(TreeNode t, int level) {
if (t == null)
return 0;
elseif (level == 0)
return 1;
else
return atDepth(t.left, level - 1) + atDepth(t.right, level - 1);
}
1