Tutorial

Binary Search Tree (BST) - Search Insert and Remove

Published on August 3, 2022
Default avatar

By Anupam Chugh

Binary Search Tree (BST) - Search Insert and Remove

While we believe that this content benefits our community, we have not yet thoroughly reviewed it. If you have any suggestions for improvements, please let us know by clicking the “report an issue“ button at the bottom of the tutorial.

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: binary search tree search recursive output

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 insert recursive output

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.

Thanks for learning with the DigitalOcean Community. Check out our offerings for compute, storage, networking, and managed databases.

Learn more about us


About the authors
Default avatar
Anupam Chugh

author

Still looking for an answer?

Ask a questionSearch for more help

Was this helpful?
 
JournalDev
DigitalOcean Employee
DigitalOcean Employee badge
May 6, 2021

this blog was awesome!! just loved it

- abhi

    JournalDev
    DigitalOcean Employee
    DigitalOcean Employee badge
    September 7, 2020

    Sir , please teach us how to implement BST in C . Also please teach us how to implement an AVL tree and Graphs using C .

    - Anushka

      Try DigitalOcean for free

      Click below to sign up and get $200 of credit to try our products over 60 days!

      Sign up

      Join the Tech Talk
      Success! Thank you! Please check your email for further details.

      Please complete your information!

      Get our biweekly newsletter

      Sign up for Infrastructure as a Newsletter.

      Hollie's Hub for Good

      Working on improving health and education, reducing inequality, and spurring economic growth? We'd like to help.

      Become a contributor

      Get paid to write technical tutorials and select a tech-focused charity to receive a matching donation.

      Welcome to the developer cloud

      DigitalOcean makes it simple to launch in the cloud and scale up as you grow — whether you're running one virtual machine or ten thousand.

      Learn more
      DigitalOcean Cloud Control Panel