Overview
A binary search tree is a binary tree that maintains the sorted ordering of its contents.
Its order property ensures that each node's value is greater than or equal to all values stored in that node's left subtree,
and is strictly less than all values stored in its right subtree.
Task: Implement an instantiable binary search tree class with multiple test methods demonstrating correctness under various circumstances.
Core BST Methods
Key implementations: insertion with duplicates handling and the critical rotation operation for tree balancing.
Recursive Insert with Duplicate Handling
protected void insertHelper(BinaryNode<T> newNode, BinaryNode<T> subtree) {
int comparison = newNode.getData().compareTo(subtree.getData());
if (comparison <= 0) {
// Insert left (duplicates go left)
if (subtree.getLeft() == null) {
subtree.setLeft(newNode);
newNode.setParent(subtree);
} else {
insertHelper(newNode, subtree.getLeft());
}
} else {
// Insert right
if (subtree.getRight() == null) {
subtree.setRight(newNode);
newNode.setParent(subtree);
} else {
insertHelper(newNode, subtree.getRight());
}
}
}
Tree Rotation (Critical for Balancing)
protected void rotate(BinaryNode<T> child, BinaryNode<T> parent) {
// Validate parent-child relationship
if (child.getParent() != parent) {
throw new IllegalArgumentException();
}
boolean isLeftRotation = child.isRightChild();
BinaryNode<T> grandparent = parent.getParent();
// Update grandparent's reference
child.setParent(grandparent);
if (grandparent != null) {
if (parent.isRightChild()) {
grandparent.setRight(child);
} else {
grandparent.setLeft(child);
}
} else {
this.root = child;
}
// Perform rotation
if (isLeftRotation) {
// Left rotation
BinaryNode<T> childLeft = child.getLeft();
parent.setRight(childLeft);
if (childLeft != null) childLeft.setParent(parent);
child.setLeft(parent);
parent.setParent(child);
} else {
// Right rotation
BinaryNode<T> childRight = child.getRight();
parent.setLeft(childRight);
if (childRight != null) childRight.setParent(parent);
child.setRight(parent);
parent.setParent(child);
}
}
📥 Download Full Implementation
Testing Rotation Correctness
@Test
public void testRotation() {
// Build tree: 10 as root, 5 as left child
bst.insert(10);
bst.insert(5);
bst.insert(15);
BinaryNode<Integer> root = bst.root;
BinaryNode<Integer> leftChild = root.getLeft();
// Perform right rotation
bst.rotate(leftChild, root);
// Verify: 5 is new root, 10 is right child
assertEquals(leftChild, bst.root);
assertEquals(root, leftChild.getRight());
}
@Test
public void testDuplicateHandling() {
bst.insert(5);
bst.insert(5); // Duplicate goes to left
bst.insert(5); // Another duplicate
assertEquals(3, bst.size());
assertTrue(bst.contains(5));
}
Complexity Analysis
Time: O(log n) average for insert/search, O(1) for rotation
Space: O(n) for n elements