Binary Search Tree in data structure

Binary Search Tree in data structure is type of tree in data structure.

In this tutorial we will see what is binary search tree, binary search tree definition, program for binary search tree.

Binary search tree definition

Binary search tree (BST) is a binary tree in which each node has value greater than every node of left subtree and less than every node of right subtree.

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

Binary search tree complexity : O(log N)

Insertion operation on Binary search tree

compare data with data of root node.
If data < data of node then compare with data of left child node and insert it to proper place.
if data > data of node then compare with data of right child node and insert it to proper place.

Deletion operation on Binary search tree

In deletion if the deleting node is leaf node then simply delete 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 Traversal

Preorder traversal

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

Inorder traversal

Traverse left subtree of root
visit root
traverse right subtree of root

Postorder traversal

traverse left subtree of root.
traverse right subtree of root
visit root

Tree traversal example

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

Lets traverse the tree using tree traversal methods in 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

Program to implement binary search tree in data structure

#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);
}

#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 in data structure

Insertion operation on Binary search tree

Deletion operation on Binary search tree

Binary Search Tree Traversal

Program to implement binary search tree in data structure

You May Also Like:

Leave a Reply Cancel reply