A One-Stop Solution for Using Binary Search Trees in Data Structure

A Binary Search Tree in data structures is a set of nodes organized in such a way that they all have the same BST characteristics. It assigns a pair of keys and values to each node. You usually employ a binary search tree for multiple indexing. Binary search trees are also good at implementing searching algorithms.

By completing this tutorial you will understand the technical fundamentals of binary search trees with all the necessary details and practical examples.

Properties of Binary Search Trees 

Binary_search_tree-properties-img1

  • The node's left subtree contains only nodes with data values lower than the parent node's data.
  • The node's right subtree contains only nodes with data higher than the parent node's data.
  • In a BST, the left and right subtree must also be a binary search tree.
  • Each node in the binary search tree can have at most two children.

These are the properties associated with BST in data structures. Next, you will explore various operations you can perform on BST in data structures.

Here's How to Land a Top Software Developer Job

Full Stack Developer - MERN StackExplore Program
Here's How to Land a Top Software Developer Job

Operations On Binary Search Trees 

Binary_search_tree-operation-img1

You can execute two operations on a binary search tree:

  • Insertion operation 
  • Deletion operation 

Let's discuss them in detail.

Insertion Operation on BST in Data Structures

Binary-Search-Trees-in-Data-Structures.

You will start with the root node. You must begin by comparing nodes with the element to be inserted. If the element to be inserted is small compared to the node's element, you must move to the left subtree. Otherwise, you will move to the right subtree.

Binary-Search-Trees-in-Data-Structures.

Code:

// A c++ program to perform insertion in binary search tree.

#include <bits/stdc++.h>

using namespace std;

// A class to create node

class Binarysearchtree

{

int data;

Binarysearchtree *left, *right;

public:

// Default constructor.

Binarysearchtree();

// Parameterized constructor.

Binarysearchtree(int);

// Insert function.

Binarysearchtree* Insert(Binarysearchtree*, int);

// Inorder traversal.

void Inorder(Binarysearchtree*);

};

// Default Constructor definition.

Binarysearchtree ::Binarysearchtree()

: data(0)

, left(NULL)

, right(NULL)

{

}

// Parameterized Constructor definition.

Binarysearchtree ::Binarysearchtree(int data1)

{

data = data1;

left = right = NULL;

}

// Insert function definition.

Binarysearchtree* Binarysearchtree ::Insert(Binarysearchtree* root, int data1)

{

if (!root)

{

//we will insert the first node, if root is NULL.

return new Binarysearchtree(data1);

}

// Insert data.

if (data1> root->data)

{

// Insert right node data, if the 'data1'

// to be inserted is larger than 'root' node data.

// Process right nodes.

root->right = Insert(root->right, data1);

}

else

{

// Insert left node data, if the 'data1'

// to be inserted is larger than 'root' node data.

// Process left nodes.

root->left = Insert(root->left, data1);

}

// Return 'root' node, after insertion.

return root;

}

// Inorder traversal function.

// This gives data in sorted order.

void Binarysearchtree ::Inorder(Binarysearchtree* root)

{

if (!root) {

return;

}

Inorder(root->left);

cout << root->data << “ ”;

Inorder(root->right);

}

// Driver code

int main()

{

Binarysearchtree bst, *root = NULL;

root = bst.Insert(root, 5);

bst.Insert(root, 3);

bst.Insert(root, 2);

bst.Insert(root, 4);

bst.Insert(root, 7);

bst.Insert(root, 6);

bst.Insert(root, 8);

cout<<"created Binary search tree: \n";

bst.Inorder(root);

return 0;

}

Binary_search_tree-insertion-img3

Become a Certified UI UX Expert in Just 5 Months!

With The Best-in-class UI UX ProgramExplore Program
Become a Certified UI UX Expert in Just 5 Months!

Deletion Operation on the Binary Search Trees in Data Structures

Binary-Search-Trees-in-Data-Structures.

When you attempt to delete a node, three scenarios might occur.

  1. Node to be deleted have no children: In this case, you can delete the node without any repercussions.
  2. Node to be deleted has precisely one child: In this case, you have to ensure that its child should be connected back to the deleted node's parent after deletion.
  3. Node to be deleted have two children: In this case, you have to search and replace the deleted node with its successor. 

Deletion-Binary-Search-Trees-in-Data-Structures

Code: 

// A C++ program to perform deletion on a BST

#include <bits/stdc++.h>

using namespace std;

struct node {

int data;

struct node *left, *right;

};

// A function to create a BST node

struct node* newNode(int key)

{

struct node* temp

= (struct node*)malloc(sizeof(struct node));

temp->data = key;

temp->left = temp->right = NULL;

return temp;

}

// A function to display BST

void display(struct node* root)

{

if (root != NULL) {

display(root->left);

cout << root->data<<" ";

display(root->right);

}

}

// A function to insert a node in the binary search tree

struct node* insert(struct node* newnode, int data)

{

// If the tree is empty, we will return a new node 

if (newnode == NULL)

return newNode(data);

/* Otherwise, recur down the tree */

if (data < newnode->data)

newnode->left = insert(newnode->left, data);

else

newnode->right = insert(newnode->right, data);

return newnode;

}

// A function returns the node with the minimum data value found in that tree.

struct node* minvalue(struct node* node)

{

struct node* temp = node;

while (temp && temp->left != NULL)

temp= temp->left;

return temp;

}

// A function to perform deletion on BST 

struct node* deleteNode(struct node* root, int data)

{

// base case

if (root == NULL)

return root;

// If the element to be deleted is smaller than the root's data, then it lies in left subtree

if (data < root->data)

root->left = deleteNode(root->left, data);

// If the element to be deleted is greater than the root's data, then it lies in right subtree

else if (data > root->data)

root->right = deleteNode(root->right, data);

// if data is same as root's data, then This is the node

// to be deleted

else {

// node has no child

if (root->left==NULL and root->right==NULL)

return NULL;

// node with either one child or no child

else if (root->left == NULL) {

struct node* t = root->right;

free(root);

return t;

}

else if (root->right == NULL) {

struct node* t = root->left;

free(root);

return t;

}

// for a node with two children, we will get the inorder successor

struct node* t = minvalue(root->right);

root->data = t->data;

// Delete the inorder successor

root->right = deleteNode(root->right, t->data);

}

return root;

}

int main()

{

// lets create an empty binary search tree

struct node* root = NULL;

root = insert(root, 5);

root = insert(root, 3);

root = insert(root, 2);

root = insert(root, 4);

root = insert(root, 7);

root = insert(root, 6);

root = insert(root, 8);

cout << "Original Binary search tree: \n";

display(root);

cout << "\n\nDelete 2\n\n";

root = deleteNode(root, 2);

cout << "modified binary search tree \n";

display(root);

cout << "\n\nDelete 5\n\n";

root = deleteNode(root, 5);

cout << "modified binary search tree \n";

display(root);

return 0;

}

Binary_search_tree-deletion-img3.

Applications of Binary Search Trees 

/Binary_search_tree-Application-img1.

  • BST are used to accomplish indexing and multi-level indexing.
  • They are also capable of implementing various search algorithms.
  • It aids in organizing a data stream.
  • Self-balancing BSTs are used to implement TreeMap and TreeSet data structures.
Advance your career as a MEAN stack developer with the Full Stack Web Developer - MEAN Stack Master's Program. Enroll now!

Next Steps

Your next stop in understanding data structures would be "AVL Trees in data structure". An AVL tree is a height-balanced BST in which the height of the left subtree and right subtree can differ at most by one.

Maybe you are looking for a more comprehensive learning of software development which can help you forge a strong career in software development. If that is indeed the case, explore Simplilearn's Post Graduate Program in Full Stack Web Development in collaboration with Caltech CTME, the behemoth university in technology education. This coding bootcamp program offers the learning, practice, and certifications that you need to not just get work-ready, but stand a chance to compete for top software development jobs anywhere in the world. 

For now, if you have questions or need clarifications regarding this "binary trees in data structures" tutorial, do let us know by leaving them in the comments section you can find at the bottom of this page. Our expert team will review and ensure that they are answered at the earliest.

About the Author

SimplilearnSimplilearn

Simplilearn is one of the world’s leading providers of online training for Digital Marketing, Cloud Computing, Project Management, Data Science, IT, Software Development, and many other emerging technologies.

View More
  • Disclaimer
  • PMP, PMI, PMBOK, CAPM, PgMP, PfMP, ACP, PBA, RMP, SP, and OPM3 are registered marks of the Project Management Institute, Inc.