Development of computational infrastructure would not become available without effective searching algorithms. One type of such algorithms is symbol tables. Term symbol table is used to describe a mechanism where we can save information (value) and later retrieve it by specified key. Symbol tables sometimes also referred as dictionaries.

There are three main classic data structures that can support efficient symbol-table implementations: binary search trees, red -black trees and hash tables.

In this article we will dive into implementation of Binary Search Tree (BST).

To better understand implementation of BST, we will use TDD to test internal implementation. To get started with tests cases, we need a skeleton of BST. BST is a recursive data structure made up of nodes. Each node contains:

• key
• value
• links to left and right nodes
• number of nodes in subtree

Each node can have only one parent except root node, which has no parent.

``````public class BinarySearchTree<Key extends Comparable<Key>, Value> {

protected Node root;

protected class Node {
protected Key key;
protected Value value;
protected Node left;
protected Node right;
protected int subtreeNodeNumber;

public Node(Key key, Value value, int subtreeNodeNumber) {
this.key = key;
this.value = value;
this.subtreeNodeNumber = subtreeNodeNumber;
}
}

public int size() {
return 0;
}

public Value get(Key key) {
return null;
}

public void put(Key key, Value value) {
return 0;
}

}
``````

This code will allow us to write tests that will fail first. Access modifiers “protected” is used for testing purposes only. In this part we will implement put, size and get functionality.

PUT

To check that put is working correctly we need next test cases:

• left node should contain item with smaller key
• right node should contain item with larger key
• left node in the subtree should contain item with smaller key
• size of BST is increased correctly
``````class BinarySearchTreeTest {

public static final String LEFT_VALUE = "leftValue";
public static final String ROOT_VALUE = "rootValue";
public static final String RIGHT_VALUE = "rightValue";
public static final int ROOT_KEY = 6;
public static final int LEFT_KEY = 4;
public static final int RIGHT_KEY = 8;
public static final int SECOND_LEFT_KEY = 7;
public static final String SECOND_LEFT_VALUE = "2LeftValue";

@Test
BinarySearchTree<Integer, String> bst = new BinarySearchTree<>();
bst.put(ROOT_KEY, ROOT_VALUE);
bst.put(LEFT_KEY, LEFT_VALUE);

assertEquals(LEFT_KEY, bst.root.left.key);
assertEquals(LEFT_VALUE, bst.root.left.value);
}

@Test
BinarySearchTree<Integer, String> bst = new BinarySearchTree<>();
bst.put(ROOT_KEY, ROOT_VALUE);
bst.put(RIGHT_KEY, RIGHT_VALUE);

assertEquals(RIGHT_KEY, bst.root.right.key);
assertEquals(RIGHT_VALUE, bst.root.right.value);
}

@Test
BinarySearchTree<Integer, String> bst = new BinarySearchTree<>();
bst.put(ROOT_KEY, ROOT_VALUE);
bst.put(RIGHT_KEY, RIGHT_VALUE);
bst.put(SECOND_LEFT_KEY, SECOND_LEFT_VALUE);

assertEquals(SECOND_LEFT_KEY, bst.root.right.left.key);
assertEquals(SECOND_LEFT_VALUE, bst.root.right.left.value);
}

@Test
void shouldReturnCorrectSizeOfBST() {
BinarySearchTree<Integer, String> bst = new BinarySearchTree<>();
bst.put(ROOT_KEY, ROOT_VALUE);
bst.put(LEFT_KEY, LEFT_VALUE);
bst.put(RIGHT_KEY, RIGHT_VALUE);

assertEquals(3, bst.size());
}
}
``````

Representation of inserted in test values would look like this:

With test cases in place we can be confident in the implementation correctness:

``````    public int size() {
return size(root);
}

private int size(Node node) {
if (node == null) {
return 0;
} else {
return node.subtreeNodeNumber;
}
}

public Value get(Key key) {
return null;
}

public void put(Key key, Value value) {
root = put(root, key, value);

}

private Node put(Node node, Key key, Value value) {
if (node == null) {
return new Node(key, value, 1);
}
int compare = key.compareTo(node.key);
if (compare < 0) {
node.left = put(node.left, key, value);
} else if (compare > 0) {
node.right = put(node.right, key, value);
} else {
node.value = value;
}
node.subtreeNodeNumber = size(node.left) + size(node.right) + 1;
return node;
}
``````

GET

For get functionality we need to check if the correct value is returned for a given key and if key is not present null is returned:

``````    @Test
void shouldGetRightValueForKey() {
BinarySearchTree<Integer, String> bst = new BinarySearchTree<>();
bst.put(ROOT_KEY, ROOT_VALUE);
bst.put(RIGHT_KEY, RIGHT_VALUE);
bst.put(SECOND_LEFT_KEY, SECOND_LEFT_VALUE);

assertEquals(RIGHT_VALUE, bst.get(RIGHT_KEY));
}

@Test
void shouldReturnNullWhenKeyIsNotPresent() {
BinarySearchTree<Integer, String> bst = new BinarySearchTree<>();
bst.put(ROOT_KEY, ROOT_VALUE);
bst.put(RIGHT_KEY, RIGHT_VALUE);
bst.put(SECOND_LEFT_KEY, SECOND_LEFT_VALUE);

assertNull(bst.get(NON_PRESENT_KEY));
}
``````

In implementation recursive call for subtree will be used again:

``````    public Value get(Key key) {
return get(root, key);
}

private Value get(Node node, Key key) {
if (node == null) {
return null;
}
int keyCmp = key.compareTo(node.key);
if (keyCmp < 0) {
return get(node.left, key);
}
if (keyCmp > 0) {
return get(node.right, key);
} else {
return node.value;
}
}
``````

Full implementation can be found on GitHub.

Sources: