Binary Search Tree (BST) - Search Insert and Remove

In this tutorial, we’ll be discussing the Binary Search Tree Data Structure. We’ll be implementing the functions to search, insert and remove values from a Binary Search Tree. We’ll implement these operations recursively as well as iteratively.

Binary Search Tree

A Binary Search tree has the following property:

• All nodes should be such that the left child is always less than the parent node.
• The right child is always greater than the parent node.

In the following sections, we’ll see how to search, insert and delete in a BST recursively as well as iteratively. Let’s create our Binary Tree Data Structure first:

public class BinaryTree {

	public TreeNode root;

	public static class TreeNode {

		public TreeNode left;
		public TreeNode right;
		public Object data;

		public TreeNode(Object data) {
			this.data = data;
			left = right = null;
		}
	}
}

Note that the above implementation is not a binary search tree because there is no restriction in inserting elements to the tree.

BST Search Recursively

The following java program contains the function to search a value in a BST recursively.

public class SearchInsertRemoveFromTree {

    public static void main(String[] args) {

	/**
	 *   Our Example Binary Search Tree
	 *       10
	 *     5    20
	 *   4  8  15 25
	 */

        BinaryTree tree = new BinaryTree();
        tree.root = new TreeNode(10);
        tree.root.left = new TreeNode(5);
        tree.root.right = new TreeNode(20);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.right = new TreeNode(8);
        tree.root.right.left = new TreeNode(15);
        tree.root.right.right = new TreeNode(25);

        System.out.println("Search Value 2 is in tree? " + searchRecursively(tree.root, 2));
        System.out.println("Search Value 10 in tree? " + searchRecursively(tree.root, 10));
    }

    public static boolean searchRecursively(TreeNode root, int value) {


        if (root == null)
            return false;


        if ((int) root.data == value)
            return true;

        if (value < (int) root.data)
            return searchRecursively(root.left, value);

        else if (value > (int) root.data)
            return searchRecursively(root.right, value);


        return false;
    }
}

The output is:

BST Search Iteratively

To search iteratively, use the following method instead:

public static boolean searchIteratively(TreeNode root, int value) {

        while (root != null) {
            if ((int) root.data == value)
                return true;

            if (value < (int) root.data)
                root = root.left;

            else
                root = root.right;
        }

        return false;
    }

Let’s look at how to insert a new node in a Binary Search Tree.

BST Insertion Recursively

public static TreeNode insertionRecursive(TreeNode root, int value) {

        if (root == null)
            return new TreeNode(value);

        if (value < (int) root.data) {
            root.left = insertionRecursive(root.left, value);
        } else if (value > (int) root.data) {
            root.right = insertionRecursive(root.right, value);
        }

        return root;

    }

public static void printInorderTraversal(TreeNode root) {
        if (root != null) {
            printInorderTraversal(root.left);
            System.out.print(root.data + " ");
            printInorderTraversal(root.right);
        }
    }

Call the above method in the main method:

tree.root = insertionRecursive(tree.root, 24);
tree.root = insertionRecursive(tree.root, 2);
printInorderTraversal(tree.root);

The tree is printed in the form of inorder traversal.

BST Insertion Iterative

To insert a Node iteratively in a BST tree, we will need to traverse the tree using two pointers.

public static TreeNode insertionIterative(TreeNode root, int value) {

        TreeNode current, parent;

        TreeNode tempNode = new TreeNode(value);

        if (root == null) {
            root = tempNode;
            return root;
        } else {
            current = root;
        }

        while (true) {
            parent = current;

            if (value < (int) current.data) {
                current = current.left;
                if (current == null) {
                    parent.left = tempNode;
                    return root;
                }

            } else if (value > (int) current.data) {
                current = current.right;

                if (current == null) {
                    parent.right = tempNode;
                    return root;
                }
            }

        }
    }

BST Removing Element Recursively

Removing an element from a BST is a little complex than searching and insertion since we must ensure that the BST property is conserved. To delete a node we need first search it. Then we need to determine if that node has children or not.

• If no children - Just delete.
• If a single child - Copy that child to the node.
• If two children - Determine the next highest element (inorder successor) in the right subtree. Replace the node to be removed with the inorder successor. Delete the inorder successor duplicate.

The inorder successor can be obtained by finding the minimum value in right child of the node.

The following java program removes elements from a BST:

public static TreeNode deleteRecursively(TreeNode root, int value) {

        if (root == null)
            return root;

        if (value < (int) root.data) {
            root.left = deleteRecursively(root.left, value);
        } else if (value > (int) root.data) {
            root.right = deleteRecursively(root.right, value);
        } else {

            if (root.left == null) {
                return root.right;
            } else if (root.right == null)
                return root.left;

            root.data = inOrderSuccessor(root.right);
            root.right = deleteRecursively(root.right, (int) root.data);
        }

        return root;

    }

    public static int inOrderSuccessor(TreeNode root) {
        int minimum = (int) root.data;
        while (root.left != null) {
            minimum = (int) root.left.data;
            root = root.left;
        }
        return minimum;
    }

Call the above delete method in the main method:

tree.root = deleteRecursively(tree.root, 4);
tree.root = deleteRecursively(tree.root, 20);
printInorderTraversal(tree.root);

The output is: 2 5 8 10 15 24 25 Let’s do the same iteratively.

BST Removing Element Iteratively

public static TreeNode deleteNodeIteratively(TreeNode root, int value) {
        TreeNode parent = null, current = root;
        boolean hasLeft = false;

        if (root == null)
            return root;

        while (current != null) {
            if ((int) current.data == value) {
                break;
            }

            parent = current;
            if (value < (int) current.data) {
                hasLeft = true;
                current = current.left;
            } else {
                hasLeft = false;
                current = current.right;
            }
        }


        if (parent == null) {
            return deleteNodeIteratively(current);
        }

        if (hasLeft) {
            parent.left = deleteNodeIteratively(current);
        } else {
            parent.right = deleteNodeIteratively(current);
        }

        return root;
    }

    private static TreeNode deleteNodeIteratively(TreeNode node) {

        if (node != null) {
            if (node.left == null && node.right == null) {
                return null;
            }

            if (node.left != null && node.right != null) {
                TreeNode inOrderSuccessor = deleteInOrderSuccessorDuplicate(node);
                node.data = inOrderSuccessor.data;
            } else if (node.left != null) {
                node = node.left;
            } else {
                node = node.right;
            }
        }

        return node;
    }

    private static TreeNode deleteInOrderSuccessorDuplicate(TreeNode node) {
        TreeNode parent = node;
        node = node.right;
        boolean rightChild = node.left == null;

        while (node.left != null) {
            parent = node;
            node = node.left;
        }

        if (rightChild) {
            parent.right = node.right;
        } else {
            parent.left = node.right;
        }

        node.right = null;
        return node;
    }

Time Complexity of BST operations is O(h). h is the height of the tree.

That brings an end to this tutorial.

You can checkout complete code and more DS & Algorithm examples from our GitHub Repository.