### Introduction to Binary Search Tree - The Coding Shala

Last Updated: 19-Jan-2021

Home >> Data Structures >> Binary Search Tree
In this post, we will learn the basic Introduction of the Binary Search Tree.

## Binary Search Tree

A binary search tree(BST), a special form of a binary tree that satisfies the following property:

- The value in each node must be greater than(or equal to) any values stored in its left subtree.
- The value in each node must be less than(or equal to) any values stored in its right subtree.

The following is an example of a binary search tree:

5

/ \

2 6

/ \ \

1 4 7

/

3

Like any other data structure, binary search trees(BSTs) support three main operations: search, insertion, and deletion.

### Search in Binary Search Tree

To search a node in the Binary search tree we can

- Return the node if the target value is equal to the value of the node.
- Continue searching in the left subtree if the target value is less than the value of the node.
- Continue searching in the right subtree if the target value is larger than the value of the node.

### Insertion in the Binary Search Tree

Another common operation in BST is to insert a new node. The main idea to insert a node is first we found out a proper leaf position for the target node and then insert the node as a leaf.

To insert a node we will:

- Search the left or right subtree according to the relation of the value of our target node.
- Repeat the above step until reaching an external node.
- Add the new node as its left or right child depending on the relation of the value of the node and the value of our target node.

### Deletion in a Binary Search Tree

Deletion is more complicated than the insertion and searching in BST. There are three different cases while we delete a node.

- If the target node has no child then we can simply remove the node.
- If the target node has one child, we can use its child to replace itself.
- If the target node has two children, replace the node with its in-order successor or predecessor node and delete that node.

**Other Posts You May Like**

- Introduction to Binary Tree
- Binary Tree Preorder Traversal
- Binary Tree Inorder Traversal
- Binary Tree Postorder Traversal
- Binary Tree Level Order Traversal

## Comments

## Post a Comment