Binary Search Tree (BST) is a linked data structure in which each node is an object. Each node contains attributes left, right, parent which points to the node corresponding to its left child, its right child and its parent respectively. If a child or parent is missing then the appropriate attribute contains the value null. Root node is the only node whose parent property is null.
Data in a binary search tree are always stored in such a way that data in each node in the left subtree is less than or equal to the data stored in its parent node. Similarly, data in each node in the right subtree is more than or equal to the data stored in its parent node.
Binary Search Tree operations
Let’s look at the common operations which can be done on binary search trees.
Insertion
public void insert(int data) {
Node node = new Node(data);
if (root == null) {
root = node;
return;
}
Node current = root;
Node parent = null;
while (current != null) {
parent = current;
if (data <= current.data) {
current = current.left;
} else {
current = current.right;
}
}
if (data <= parent.data) {
parent.left = node;
} else {
parent.right = node;
}
node.parent = parent;
}As talked above about how nodes are arranged in a BST, inserting a new node is fairly simple. We first check if the tree is empty. If it is, we just set the root of the tree to point to the new node. If not, we first traverse to the appropriate position and insert the new node.
Deletion
There are 3 scenarios which can happen when deleting a node in BST. Let the node to be deleted be x.
- x does not have a left child – In this case we just replace x with its right child (Figure 1).
- x does not have a right child – In this case we replace x with its left child (Figure 2).
- x has both left and right child – In this case we replace x with its successor s, which lies in the x’s right subtree and has no left child (i.e., minimum of the x’s right subtree). We take out s from its position and replace x with it. Now, there can be two positions where s can be situated.
- s is the right child of x – We just replace x with s (Figure 3).
- s lies in the right subtree of x but is not the right child of x – In this case we first replace s with its right child and then replace x with s (Figure 4 (a, b, c)).
public int delete(int data) throws Exception {
Node toBeDeleted = findNode(data);
if (toBeDeleted == null) {
throw new Exception("Node with given data didn't exist");
}
if (toBeDeleted.left == null) {
replaceSubTree(toBeDeleted, toBeDeleted.right);
} else if (toBeDeleted.right == null) {
replaceSubTree(toBeDeleted, toBeDeleted.left);
} else {
Node smallest = toBeDeleted.right;
while (smallest.left != null) {
smallest = smallest.left;
}
if (smallest.parent != toBeDeleted) {
replaceSubTree(smallest, smallest.right);
smallest.right = toBeDeleted.right;
smallest.right.parent = smallest;
}
replaceSubTree(toBeDeleted, smallest);
smallest.left = toBeDeleted.left;
smallest.left.parent = smallest;
}
return toBeDeleted.data;
}Pre order traversal
In pre order traversal or walk, we first process a node, its left subtree and then the right subtree.
public void walkPreOrder() {
walkPreOrder(root);
}
private void walkPreOrder(Node current) {
if (current == null) {
return;
}
System.out.print(current.data + " ");
walkPreOrder(current.left);
walkPreOrder(current.right);
}In order traversal
In in-order traversal, we first process the left subtree of node, the node itself and then the right subtree.
public void walkInOrder() {
walkInOrder(root);
}
private void walkInOrder(Node current) {
if (current == null) {
return;
}
walkInOrder(current.left);
System.out.print(current.data + " ");
walkInOrder(current.right);
}Post order traversal
In post order traversal, we first process the left subtree of node, its right subtree and then the node itself.
public void walkPostOrder() {
walkPostOrder(root);
}
private void walkPostOrder(Node current) {
if (current == null) {
return;
}
walkPostOrder(current.left);
walkPostOrder(current.right);
System.out.print(current.data + " ");
}Minimum in a tree
Finding the minimum in a tree is quite easy in a BST as we have to keep jumping to the left child starting from the root node till, we find a node whose left is set to null.
public int getMinimum() {
Node current = root;
while (current.left != null) {
current = current.left;
}
return current.data;
}Maximum in a tree
To find the maximum in a tree, we keep traversing to the right subtree starting from the root until we find a node whose right child is set to null.
public int getMaximum() {
Node current = root;
while (current.right != null) {
current = current.right;
}
return current.data;
}Complete program implementing a BST
Binary Search Tree class in Java
package com.theaconitedev;
public class BinarySearchTree {
private Node root;
private class Node {
public Node parent;
public int data;
public Node left;
public Node right;
public Node(int data) {
this.data = data;
}
}
public void insert(int data) {
Node node = new Node(data);
if (root == null) {
root = node;
return;
}
Node current = root;
Node parent = null;
while (current != null) {
parent = current;
if (data <= current.data) {
current = current.left;
} else {
current = current.right;
}
}
if (data <= parent.data) {
parent.left = node;
} else {
parent.right = node;
}
node.parent = parent;
}
private Node findNode(int data) {
if (root == null) {
return null;
}
Node current = root;
while (current != null) {
if (current.data == data) {
break;
}
if (data <= current.data) {
current = current.left;
} else {
current = current.right;
}
}
return current;
}
private void replaceSubTree(Node oldSubTreeRoot, Node newSubTreeRoot) {
if (oldSubTreeRoot.parent == null) {
root = newSubTreeRoot;
} else if (oldSubTreeRoot == oldSubTreeRoot.parent.left) {
oldSubTreeRoot.parent.left = newSubTreeRoot;
} else {
oldSubTreeRoot.parent.right = newSubTreeRoot;
}
if (newSubTreeRoot != null) {
newSubTreeRoot.parent = oldSubTreeRoot.parent;
}
}
public int delete(int data) throws Exception {
Node toBeDeleted = findNode(data);
if (toBeDeleted == null) {
throw new Exception("Node with given data didn't exist");
}
if (toBeDeleted.left == null) {
replaceSubTree(toBeDeleted, toBeDeleted.right);
} else if (toBeDeleted.right == null) {
replaceSubTree(toBeDeleted, toBeDeleted.left);
} else {
Node smallest = toBeDeleted.right;
while (smallest.left != null) {
smallest = smallest.left;
}
if (smallest.parent != toBeDeleted) {
replaceSubTree(smallest, smallest.right);
smallest.right = toBeDeleted.right;
smallest.right.parent = smallest;
}
replaceSubTree(toBeDeleted, smallest);
smallest.left = toBeDeleted.left;
smallest.left.parent = smallest;
}
return toBeDeleted.data;
}
public void walkPreOrder() {
walkPreOrder(root);
}
private void walkPreOrder(Node current) {
if (current == null) {
return;
}
System.out.print(current.data + " ");
walkPreOrder(current.left);
walkPreOrder(current.right);
}
public void walkInOrder() {
walkInOrder(root);
}
private void walkInOrder(Node current) {
if (current == null) {
return;
}
walkInOrder(current.left);
System.out.print(current.data + " ");
walkInOrder(current.right);
}
public void walkPostOrder() {
walkPostOrder(root);
}
private void walkPostOrder(Node current) {
if (current == null) {
return;
}
walkPostOrder(current.left);
walkPostOrder(current.right);
System.out.print(current.data + " ");
}
public int getMinimum() {
Node current = root;
while (current.left != null) {
current = current.left;
}
return current.data;
}
public int getMinimumRecursive() {
return getMinimumRecursive(root);
}
private int getMinimumRecursive(Node current) {
if (current.left == null) {
return current.data;
}
return getMinimumRecursive(current.left);
}
public int getMaximum() {
Node current = root;
while (current.right != null) {
current = current.right;
}
return current.data;
}
public int getMaximumRecursive() {
return getMaximumRecursive(root);
}
private int getMaximumRecursive(Node current) {
if (current.right == null) {
return current.data;
}
return getMaximumRecursive(current.right);
}
}
Main
package com.theaconitedev;
import java.util.Scanner;
public class BinarySearchTreeImplementation {
public static void main(String[] args) {
BinarySearchTree bst = new BinarySearchTree();
System.out.println("Adding below numbers in the binary search tree");
for (int i = 1; i <= 10; i++) {
int randomNumber = (int) (Math.random() * 100);
System.out.print(randomNumber + " ");
bst.insert(randomNumber);
}
System.out.println();
System.out.println("Pre order traversal");
bst.walkPreOrder();
System.out.println();
System.out.println("In order traversal");
bst.walkInOrder();
System.out.println();
System.out.println("Post order traversal");
bst.walkPostOrder();
System.out.println();
System.out.println("Minimum number in the tree = " + bst.getMinimum());
System.out.println("Minimum number in the tree (recursive) = " + bst.getMinimumRecursive());
System.out.println("Maximum number in the tree = " + bst.getMaximum());
System.out.println("Maximum number in the tree (recursive) = " + bst.getMaximumRecursive());
try (Scanner scanner = new Scanner(System.in)) {
System.out.print("Enter a number to delete: ");
int toDelete = scanner.nextInt();
scanner.nextLine();
bst.delete(toDelete);
bst.walkInOrder();
} catch (Exception ex) {
System.out.println(ex.getMessage());
}
}
}
Output
Adding below numbers in the binary search tree 79 22 0 48 25 16 20 41 19 38 Pre order traversal 79 22 0 16 20 19 48 25 41 38 In order traversal 0 16 19 20 22 25 38 41 48 79 Post order traversal 19 20 16 0 38 41 25 48 22 79 Minimum number in the tree = 0 Minimum number in the tree (recursive) = 0 Maximum number in the tree = 79 Maximum number in the tree (recursive) = 79 Enter a number to delete: 25 0 16 19 20 22 38 41 48 79