When we are talking about data structures, we cannot forget the name is Tree. The tree is an essential Data Structure, helpful in hierarchically storing data. When we talk about trees in detail, the classification of trees is necessary to discuss. For now, we will only discuss one classification of the tree, i.e., the Binary Search Tree.

This article will help us understand the Binary Search Tree and its properties. So let's start to enhance our knowledge about Binary Search Trees.

Binary Search Tree

The first word of â€˜Binary Search Treesâ€™, namely â€˜Binaryâ€™, tells us that every node in the tree can have two children: the left child and the right child. The data of the right child and the left child must be greater and smaller than the data of the parent node, respectively.

Lets us see an example of a binary search tree.

In this BST, we can observe that the left child of every node has a value less than its parent node, and the right child of every node has a value greater than its parent node.

Now let us understand the procedure to insert and delete a node into the Binary Search Tree.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Inserting a node into Binary Search Tree

Consider a Binary Search Tree â€˜Tâ€™ and an arbitrary node â€˜Nâ€™ having value stored as â€˜Valâ€™. Below is the procedure to insert the node â€˜Nâ€™ into â€˜Tâ€™.

First, we will compare the value â€˜Valâ€™ with the data stored in the root node.

If â€˜Valâ€™ is greater than the root node's value, we will move to its right subtree.

If â€˜Valâ€™ is smaller than the root node's value, we will move to its left subtree.

We will repeat the first to third step until the current root node does not have left and right subtree.

Now, if â€˜Valâ€™ is smaller than the value of the current root node, we will insert node â€˜Nâ€™ as its left child.

Else if â€˜Valâ€™ is greater than the value of the current root node, we will insert node â€˜Nâ€™ as its right child.

Now let us try inserting a node with â€˜Valâ€™ equal to 5 into the above tree.

Comparing the value â€˜5â€™ from the value of the root and finding it to be greater, so moving to the right subtree.

Comparing the value â€˜5â€™ from the value of the current root and finding it to be smaller, so moving to the left subtree.

Comparing the value â€˜5â€™ from the value of the current root and finding it to be greater, so moving to the right subtree.

On finding the current root without any subtree, we will insert the node â€˜Nâ€™ as the right child.

Deleting a node from a Binary Search Tree

Let us consider a Binary Search Tree â€˜Tâ€™ and the node to be deleted as â€˜Nâ€™. Deletion of a node can be classified based on the number of children of the node to be deleted.

1. â€˜Nâ€™ has no children

When the node â€˜Nâ€™ has no children, we can simply replace it will the null value. For Example, the node with the value as â€˜8â€™ is to be removed in the tree below.

Simply the node with the value â€˜8â€™ can be removed.

2. â€˜Nâ€™ has one child

When the node â€˜Nâ€™ has only one child, we can replace it with its only child. For Example, the node having the value as â€˜4â€™ is removed in the below tree.

Simply the node with the value â€˜4â€™ can be replaced with its only child, and then the replaced node will be removed.

3. â€˜Nâ€™ has two children

When node â€˜Nâ€™ has both children, we will need to determine the immediate predecessor. To find the immediate predecessor, we need to move to the left child of the node â€˜Nâ€™ and then keep moving to the right child of the current node unless there is no right child. Then the node we have is the immediate predecessor.

Now this immediate predecessor can be replaced with the node â€˜Nâ€™. And then, the replaced node can be removed with the first or second method defined above accordingly. For Example, the node with the value as â€˜7â€™ is to be removed in the tree below.

We will have to find its immediate predecessor to replace it with. The node with the value â€˜5â€™ is the immediate predecessor with the above algorithm.

The node â€˜Nâ€™ will be replaced with the immediate predecessor.

And then, the replaced node will be removed.

FAQs

What is a tree? A tree is a data structure that stores data in the form of nodes to maintain a hierarchy.

What do you understand from the term Binary Search Tree? A binary Search Tree is that classification of Trees in which every node in the tree can have at most two children, the left child, and the right child. The data of the right child and the left child must be greater and smaller than the data of the parent node, respectively.

How many maximum children can each Binary Search Tree node have? The Binary Search Tree node can have a maximum of two children. The children are called left and right children.

What property must every child node have to follow in a Binary Search Tree? The property that every child node has to follow is that if it is a left child, its value should be smaller than the parent node, and if it is a right child, its value should be greater than the parent node.

What is the method to find the immediate predecessor? To find the immediate predecessor, we need to move to the left child of the node â€˜Nâ€™ and then keep moving to the right child of the current node unless there is no right child. Then the node we have is the immediate predecessor.

Key Takeaways

In the above article, we have learned about Binary Search Trees and their properties. We also covered the method to insert a new node and delete a specific node from it.