Binary Search Tree (BST) - Search Insert and Remove With Examples

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:

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.

The output is:

bst-search-recursive-output (1)

BST Search Iteratively

To search iteratively, use the following method instead:

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

BST Insertion Recursively

Call the above method in the main method:

The tree is printed in the form of inorder traversal.

bst-search-recursive-output (1)

BST Insertion Iterative

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

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:

Call the above delete method in the main method:

The output is:
2 5 8 10 15 24 25

Let’s do the same iteratively.

BST Removing Element Iteratively

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.

By admin

Leave a Reply

%d bloggers like this: