Implementing Binary Search Tree

Implementing Binary Search Tree

  • A common variant of binary tree is a binary search tree.
  • A binary search tree matches the search speed of arrays.
  • It offers efficient insertions and deletions as in the case of a linked list.
Binary search tree is a binary tree in which every node satisfies the following conditions:
  • All values in the left subtree of a node are less than the value of the node.
  • All values in the right subtree of a node are greater than the value of the node.

You can implement various operations on a binary search tree:

  • Traversal
  • Search
  • Insert
  • Delete
Inserting Nodes in a Binary Search Tree 
  • Before inserting a node in a binary search tree, you first need to check whether the tree is empty or not.
  • If the tree is empty, make the new node as root.
  • If the tree is not empty, you need to locate the appropriate position for the new node to be inserted.
  • This requires you to locate the parent of the new node to be inserted.
  • Once the parent is located, the new node is inserted as the left child or right child of the parent.
  • To locate the parent of the new node to be inserted, you need to implement a search operation on the tree.
Algorithm to locate the parent of the new node to be inserted:
1.	Mark the root node as currentNode.
2.	Make parent point to NULL.
3.	Repeat steps 4, 5, and 6 until currentNode becomes NULL.
4.	Make parent point to currentNode.
5.	If the value of the new node is less than or equal to that of currentNode:
	Make currentNode point to its 
left child.
6.	If the value of the new node is greater than that of currentNode:
Make currentNode point to its  
right child.
Algorithm to insert a node in a binary search tree:
1.	Allocate memory for the new node.
2.	Assign value to the data field of new node.
3.	Make the left and right child of the new node point to NULL.
4.	Locate the node which will be the parent of the node to be inserted. Mark it as parent.
5.	If parent is NULL (Tree is empty):
a.	Mark the new node as ROOT.
b.	Exit.
6.	If the value in the data field of new node is less than that of parent:
a.	Make the left child of parent point to the new node.
b.	Exit.
7.	If the value in the data field of the new node is greater than that of the parent:
a.	Make the right child of parent point to 
Deleting Nodes from a Binary Search Tree
  • Delete operation in a binary search tree refers to the process of deleting the specified node from the tree.
  • Before implementing a delete operation, you first need to locate the position of the node to be deleted and its parent.
  • To locate the position of the node to be deleted and its parent, you need to implement a search operation. 
CCC Online Test 2021 CCC Practice Test Hindi Python Programming Tutorials Best Computer Training Institute in Prayagraj (Allahabad) Best Java Training Institute in Prayagraj (Allahabad) Best Python Training Institute in Prayagraj (Allahabad) O Level Online Test in Hindi Bank SSC Railway TET UPTET Question Bank career counselling in allahabad Sarkari Naukari Notification Best Website and Software Company in Allahabad Sarkari Exam Quiz