Binary Search Tree in Data structure is a type of tree with N number of nodes connected by edges based on some condition.

Binary Search Tree in Data structure

Binary search tree definition: Binary search tree (BST) is a binary tree in which each node has a value greater than every node of left subtree and less than every node of right subtree.
The main property for Binary Search Tree in Data Structure
The Left subtree of a node contains only nodes with key lesser than that of the root node.
The right subtree of a node contains only nodes with key greater than that of the root node.

It is a very useful data structure in which item can be searched in O(log N) where N is the number of nodes.

Binary Search Tree Traversal

1. Preorder traversal

  • Visit the root
  • Traverse the left subtree of root.
  • Traverse right subtree of root

2. Inorder traversal

  • Traverse left subtree of root
  • visit root
  • Traverse right subtree of root

3. Postorder traversal

  • Traverse left subtree of root.
  • Traverse right subtree of root
  • visit root

Tree Traversal example

Consider tree with A,B,D,E,F,G nodes of tree.

BSTLet us traverse the tree using tree traversal methods in a data structure.
Preorder traversal = A B E G D F
Inorder traversal = E B G A F D
Postorder traversal = E G B F D A

Binary Search Tree example

Binary Search Tree in Data Structure
Binary Search Tree in Data Structure

Operations on binary search tree

There are different operations we can perform on the binary search tree which are as follows:

Binary search tree Insertion

  • Compare data with data of the root node.
  • If data < data of node then compare with data of left child node and insert it to the proper place.
  • if data > data of node then compare with data of right child node and insert it to proper place.
  • Example:-

 

Binary search tree Deletion

  • In deletion, if the deleting node is leaf node then simply delete the node.
  • If the node which is deleting has some child then after deleting the node adjust its child according to the Binary search tree properly.

 

Binary Search Tree algorithm

1. Searching in Binary search tree

  1. Input Search key
  2. If search key = root Node, Return Root Node
  3. If Search key > root, recur at the right subtree
  4. If Search key < root, recur at the left subtree

Example:-    Search 5 in Tree

Searching in Binary Search Tree
Searching in Binary Search Tree

2. Insertion in Binary search tree

Insertion is done at the leaf node

  1. Check for key till leaf node
  2. If leaf node encounters, Add node

Example:-  Insert 7

Insertion in Binary search tree
Insertion in Binary search tree

3. Deletion in Binary search tree

To delete the node from binary search tree there are different possibility arise which are as follow

  • If Node to be deleted is a leaf node, Go to leaf and delete Node

Example:-  Delete 5

Deletion in Binary search tree

    Deletion in Binary search tree
  • If Node to be deleted has one child, Copy child node to Node and delete child node.

Example:- Delete 3

Deletion in Binary search tree
Deletion in Binary search tree
  • If Node to be deleted has two children, Find inorder successor of the node. Copy contents of the inorder successor to the node and delete the inorder successor.

Example:- Delete 10

Deletion in Binary search tree
Deletion in Binary search tree

Note: inorder successor is needed only when the right child is not empty. In this particular case, the inorder successor can be obtained by finding the minimum value in right child of the node

Binary search tree program in c

#include<stdio.h>
#include<stdlib.h>

struct node
{
int data;
struct node* left;
struct node* right;
};

struct node* createNode(value){
struct node* newNode = malloc(sizeof(struct node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;

return newNode;
}

struct node* insert(struct node* root, int data)
{
if (root == NULL) return createNode(data);

if (data < root->data)
root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);

return root;
}

void inorder(struct node* root){
if(root == NULL) return;
inorder(root->left);
printf("%d ->", root->data);
inorder(root->right);
}

int main(){
struct node *root = NULL;
root = insert(root, 8);
insert(root, 3);
insert(root, 1);
insert(root, 6);
insert(root, 7);
insert(root, 10);
insert(root, 14);
insert(root, 4);
printf("Binary search tree\n");
inorder(root);
}

Output:
Binary Search Tree(BST)Binary search tree complexity

1. Searching
The worst time complexity for Binary search tree is O(h) where h is the height of the tree
The average and best case complexity for Binary search tree are O(log N).
2. Insertion
The insertion takes place at a leaf node in the tree so worst-case complexity for insertion is O(h).
3. Deletion
The worst-case complexity for deletion is O(h).

Write A Comment