Coding Implementations
Complete Binary Search Tree Implementation
public class BinarySearchTree {
private TreeNode root;
private class TreeNode {
int value;
TreeNode left;
TreeNode right;
TreeNode(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// Insert a new node
public void insert(int value) {
root = insertRecursive(root, value);
}
private TreeNode insertRecursive(TreeNode current, int value) {
if (current == null) {
return new TreeNode(value);
}
if (value < current.value) {
current.left = insertRecursive(current.left, value);
} else if (value > current.value) {
current.right = insertRecursive(current.right, value);
}
return current;
}
}
Traversal Methods Implementation
Recursive Traversal Methods
public class BinarySearchTree {
// In-order Traversal
public void inOrderTraversal() {
inOrderTraversal(root);
}
private void inOrderTraversal(TreeNode node) {
if (node != null) {
inOrderTraversal(node.left);
System.out.print(node.value + " ");
inOrderTraversal(node.right);
}
}
// Pre-order Traversal
public void preOrderTraversal() {
preOrderTraversal(root);
}
private void preOrderTraversal(TreeNode node) {
if (node != null) {
System.out.print(node.value + " ");
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}
// Post-order Traversal
public void postOrderTraversal() {
postOrderTraversal(root);
}
private void postOrderTraversal(TreeNode node) {
if (node != null) {
postOrderTraversal(node.left);
postOrderTraversal(node.right);
System.out.print(node.value + " ");
}
}
}
Iterative Traversal Implementations
import java.util.Stack;
public class BinarySearchTree {
// Iterative In-order Traversal
public void iterativeInOrder() {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
TreeNode current = root;
while (current != null || !stack.isEmpty()) {
while (current != null) {
stack.push(current);
current = current.left;
}
current = stack.pop();
System.out.print(current.value + " ");
current = current.right;
}
}
// Iterative Pre-order Traversal
public void iterativePreOrder() {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.value + " ");
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
}
Search and Deletion Methods
public class BinarySearchTree {
// Search a value
public boolean search(int value) {
return searchRecursive(root, value);
}
private boolean searchRecursive(TreeNode current, int value) {
if (current == null) {
return false;
}
if (value == current.value) {
return true;
}
return value < current.value
? searchRecursive(current.left, value)
: searchRecursive(current.right, value);
}
// Delete a node
public void delete(int value) {
root = deleteRecursive(root, value);
}
private TreeNode deleteRecursive(TreeNode current, int value) {
if (current == null) {
return null;
}
if (value == current.value) {
// Node with no children
if (current.left == null && current.right == null) {
return null;
}
// Node with only one child
if (current.right == null) {
return current.left;
}
if (current.left == null) {
return current.right;
}
// Node with two children
int smallestValue = findSmallestValue(current.right);
current.value = smallestValue;
current.right = deleteRecursive(current.right, smallestValue);
return current;
}
if (value < current.value) {
current.left = deleteRecursive(current.left, value);
return current;
}
current.right = deleteRecursive(current.right, value);
return current;
}
private int findSmallestValue(TreeNode root) {
return root.left == null ? root.value : findSmallestValue(root.left);
}
}
Tree Complexity Analysis
Operation |
Average Case |
Worst Case |
Search |
O(log n) |
O(n) |
Insertion |
O(log n) |
O(n) |
Deletion |
O(log n) |
O(n) |
Best Practices
- Always balance your tree to maintain O(log n) operations
- Use iterative methods for large trees to prevent stack overflow
- LabEx recommends practicing these implementations to master tree traversal techniques