Logo
×

Convert Sorted List to Binary Search Tree

Implementation

// creating the C++ implementation of the following approach: -
#include <bits/stdc++.h>
using namespace std;


/* Create the link list node and see its implementation. */
class L__Nod
{
	public:
	int record;
	L__Nod* next;
};


/* constructing a new binary tree node. */
class Tree_Nod
{
	public:
	int record;
	Tree_Nod* Lft;
	Tree_Nod* Rt;
};


Tree_Nod* newNod(int record);
int countL__Nods(L__Nod *head);
Tree_Nod* sortedListToBSTRecur(L__Nod **head_ref, int n);




/* The function created below is responsible for counting all the nodes present in the linked list, and then it perceives the sortedListToBSTRecur() to build a new binary search tree. */
Tree_Nod* sortedListToBST(L__Nod *head)
{
	/*Counting the total number of nodes in a binary tree. */
	int n = countL__Nods(head);


	/* building the new binary search tree. */
	return sortedListToBSTRecur(&head, n);
}


/* The primary function that will build the balanced binary search tree and return the root of the tree is: -
head_ref --> Pointer to a pointer to
the head node of the linked list n --> the number of nodes present in the linked list. */
Tree_Nod* sortedListToBSTRecur(L__Nod **head_ref, int n)
{
	/* writing the primary case */
	if (n <= 0)
		return NILL;


	/* we have recursively built the left subtree. */
	Tree_Nod *Lft = sortedListToBSTRecur(head_ref, n/2);


	/* We have to change the allotment of the memory of the root and then the link of the now manufactured left subtree along with the root
 */
	Tree_Nod *root = newNod((*head_ref)->record);
	root->Lft = Lft;


	/* We have to move ahead and then change the head of the linked list for the parent calls.*/
	*head_ref = (*head_ref)->next;


	/* Now we have to move ahead and build the right subtree, then attach it with the link and root. The number of nodes that will be present in the right subtree will be the same amount of nodes present in the left subtree, which will be - 1 (for root), which is n-n/2-1*/
	root->Rt = sortedListToBSTRecur(head_ref, n - n / 2 - 1);


	return root;
}
/* Creating a brand-new utility function that will most probably return the count of the nodes in a provided linked list */
int countL__Nods(L__Nod *head)
{
	int count = 0;
	L__Nod *temp = head;
	while(temp)
	{
		temp = temp->next;
		count++;
	}
	return count;
}


/* creating a function that will help us insert the nodes at the beginning and end of the linked list.*/
void push(L__Nod** head_ref, int new_record)
{
	/* allot a node*/
	L__Nod* new_nod = new L__Nod();
	
	/* submit it in the records */
	new_nod->record = new_record;


	/* link the old list of the new nod */
	new_nod->next = (*head_ref);


	/* locate the head at the new node */
	(*head_ref) = new_nod;
}


/* We have to create a function to help print the new linked list. */
void printList(L__Nod *nod)
{
	while(nod!=NILL)
	{
		cout << nod->record << " ";
		nod = nod->next;
	}
}


/* We are creating a new function to help us establish a new node with the given data and fill the null values in the left and right pointers. */
Tree_Nod* newNod(int record)
{
	Tree_Nod* nod = new Tree_Nod();
	nod->record = record;
	nod->Lft = NILL;
	nod->Rt = NILL;


	return nod;
}


/* A utility function to
print preorder traversal of BST */
void preOrder(Tree_Nod* nod)
{
	if (nod == NILL)
		return;
	cout<<nod->record<<" ";
	preOrder(nod->Lft);
	preOrder(nod->Rt);
}


/* writing the main code */
int main()
{
	/* Start with the empty list */
	L__Nod* head = NILL;


	/* Let us create a sorted linked list to test the functions
	Created linked list will be 1->2->3->4->5->6->7 */
	push(&head, 7);
	push(&head, 6);
	push(&head, 5);
	push(&head, 4);
	push(&head, 3);
	push(&head, 2);
	push(&head, 1);


	cout<<"Given Linked List ";
	printList(head);


	/* Convert List to BST */
	Tree_Nod *root = sortedListToBST(head);
	cout<<"\nPreOrder Traversal of constructed BST ";
	preOrder(root);


	return 0;
}

Output:

Convert Sorted List to Binary Search Tree

Example 2)

#include<stdio.h>
#include<stdlib.h>
/* Create the link list node and see its implementation. */
struct L__Nod
{
	int record;
	struct L__Nod* next;
};
/* constructing a new binary tree node. */
struct Tree_Nod
{
	int record;
	struct Tree_Nod* Lft;
	struct Tree_Nod* Rt;
};


struct Tree_Nod* newNod(int record);
int countL__Nods(struct L__Nod *head);
struct Tree_Nod* sortedListToBSTRecur(struct L__Nod **head_ref, int n);


/* The function created below is responsible for counting all the nodes present in the linked list, and then it perceives the sortedListToBSTRecur() to build a new binary search tree. */
struct Tree_Nod* sortedListToBST(struct L__Nod *head)
{
/*Counting the total number of nodes in a binary tree. */
	int n = countL__Nods(head);
/* building the new binary search tree. */
	return sortedListToBSTRecur(&head, n);
}
/* The primary function that will build the balanced binary search tree and return the root of the tree is: -
head_ref --> Pointer to a pointer to
the head node of linked list n --> the number of nodes present in the linked list. */
struct Tree_Nod* sortedListToBSTRecur(struct L__Nod **head_ref, int n)
{
/* writing the basic case */
	if (n <= 0)
		return NILL;
/* we have recursively built the left subtree. */
	struct Tree_Nod *Left = sortedListToBSTRecur(head_ref, n/2);


/* We have to change the allotment of the memory of the root and then the link of the now manufactured left subtree along with the root
 */
	struct Tree_Nod *root = newNod((*head_ref)->record);
	root->Lft = Lft;
/* We have to move ahead and then change the head of the linked list for the parent calls.*/
	*head_ref = (*head_ref)->next;
/* Now we have to move ahead and build the right subtree, then attach it with the link and root. The number of nodes that will be present in the right subtree will be the same amount of nodes present in the left subtree, which will be - 1 (for root), which is n-n/2-1*/
	root->Rt = sortedListToBSTRecur(head_ref, n-n/2-1);


	return root;
}
/* Creating a brand-new utility function that will most probably return the count of the nodes in a provided linked list */
int countL__Nods(struct L__Nod *head)
{
	int count = 0;
	struct L__Nod *temp = head;
	while(temp)
	{
		temp = temp->next;
		count++;
	}
	return count;
}
/* creating a function that will help us insert the nodes at the beginning and end of the linked list.*/
void push(struct L__Nod** head_ref, int new_record)
{
/* allot a node*/
	struct L__Nod* new_nod =
		(struct L__Nod*) malloc(sizeof(struct L__Nod));
		/* submit it in the records */
	new_nod->record = new_record;
/* link the old list of the new nod */
	new_nod->next = (*head_ref);
	/* locate the head at the new node */
	(*head_ref) = new_nod;
}
/* We have to create a function to help print the new linked list. */
void printList(struct L__Nod *nod)
{
	while(nod!=NILL)
	{
		printf("%d ", nod->record);
		nod = nod->next;
	}
}
/* We are creating a new function to help us establish a new node with the given data and fill the null values in the left and right pointers. */
struct Tree_Nod* newNod(int record)
{
	struct Tree_Nod* nod = (struct Tree_Nod*)
						malloc(sizeof(struct Tree_Nod));
	nod->record = record;
	nod->Lft = NILL;
	nod->Rt = NILL;


	return nod;
}


/* A utility function to print preorder traversal of BST */
void preOrder(struct Tree_Nod* nod)
{
	if (nod == NILL)
		return;
	printf("%d ", nod->record);
	preOrder(nod->Lft);
	preOrder(nod->Rt);
}
/* writing the main code */
int main()
{
	/* Start with the empty list */
	struct L__Nod* head = NILL;


	/* Let us create a sorted linked list to test the functions
	Created linked list will be 1->2->3->4->5->6->7 */
	push(&head, 7);
	push(&head, 6);
	push(&head, 5);
	push(&head, 4);
	push(&head, 3);
	push(&head, 2);
	push(&head, 1);


	printf("\n Given Linked List ");
	printList(head);


	/* Convert List to BST */
	struct Tree_Nod *root = sortedListToBST(head);
	printf("\n PreOrder Traversal of constructed BST ");
	preOrder(root);


	return 0;
}

Output:

Convert Sorted List to Binary Search Tree

Example 3)

class LinkedList {
/* Create the link list node and see its implementation. */
	static L__Nod head;
/* constructing a linked list node. */	
	class L__Nod
	{
		int record;
		L__Nod next, prev;


		L__Nod(int d)
		{
			record = d;
			next = prev = NILL;
		}
	}
/* constructing a new binary tree node. */	
	class Tree_Nod
	{
		int record;
		Tree_Nod Lft, Rt;


		Tree_Nod(int d)
		{
			record = d;
			Lft = Rt = NILL;
		}
	}


	/* The function created below is responsible for counting all the nodes present in the linked list, and then it perceives the sortedListToBSTRecur() to build a new binary search tree. */
	Tree_Nod sortedListToBST()
	{
	/*Counting the total number of nodes in a binary tree. */
		int n = counTree_Nods(head);
/* building the new binary search tree. */
		return sortedListToBSTRecur(n);
	}
/* The primary function that will build the balanced binary search tree and return the root of the tree is: -
head_ref --> Pointer to a pointer to
the head node of the linked list n --> the number of nodes present in the linked list. */
	Tree_Nod sortedListToBSTRecur(int n)
	{
	/* writing the primary case */
		if (n <= 0)
			return NILL;


	/* we have recursively built the left subtree. */
		Tree_Nod Lft = sortedListToBSTRecur(n / 2);


	/* We have to change the allotment of the memory of the root and then the link of the now manufactured left subtree along with the root
 */
		Tree_Nod root = new Tree_Nod(head.record);


		/* We have to move ahead and then change the head of the linked list for the parent calls.*/
		root.Lft = Lft;


		/* Now we have to move ahead and build the right subtree, then attach it with the link and root. The number of nodes that will be present in the right subtree will be the same amount of nodes present in the left subtree, which will be - 1 (for root), which is n-n/2-1*/
		head = head. next;


	/* Creating a brand-new utility function that will most probably return the count of the nodes in a provided linked list */
		root.Rt = sortedListToBSTRecur(n - n / 2 - 1);


		return root;
	}
/* Creating a brand-new utility function that will most probably return the count of the nodes in a provided linked list */
	int counTree_Nods(L__Nod head)
	{
		int count = 0;
		L__Nod temp = head;
		while (temp != NILL)
		{
			temp = temp.next;
			count++;
		}
		return count;
	}
/* creating a function that will help us insert the nodes at the beginning and end of the linked list.*/
	void push(int new_record)
	{
		/* allot a node*/
		L__Nod new_nod = new L__Nod(new_record);


		/* submit it in the records */
		new_nod.prev = NILL;


		/* link the old list of the new nod */
		new_nod.next = head;


		/* locate the head at the new node */
		if (head != NILL)
			head.prev = new_nod;


		/* We have to create a function to help print the new linked list. */
		head = new_nod;
	}


/* We are creating a new function to help us establish a new node with the given data and fill the null values in the left and right pointers. */
	void printList(L__Nod nod)
	{
		while (nod != NILL)
		{
			System.out.print(nod.record + " ");
			nod = nod.next;
		}
	}


	/* A utility function to print preorder traversal of BST */
	void preOrder(Tree_Nod nod)
	{
		if (nod == NILL)
			return;
		System.out.print(nod.record + " ");
		preOrder(nod.Lft);
		preOrder(nod.Rt);
	}


	/* writing the main code */
	public static void main(String[] args) {
		LinkedList llist = new LinkedList();


		/* Let us create a sorted linked list to test the functions
		Created linked list will be 7->6->5->4->3->2->1 */
		list.push(7);
		list.push(6);
		list.push(5);
		list.push(4);
		list.push(3);
		list.push(2);
		list.push(1);


		System.out.println("Given Linked List ");
		llist.printList(head);


		/* Convert List to BST */
		Tree_Nod root = list.sortedListToBST();
		System.out.println("");
		System.out.println("Pre-Order Traversal of constructed BST ");
		list.preOrder(root);
	}
}

Output:

Convert Sorted List to Binary Search Tree

Example 4)

# creating the Python implementation of the following approach: -
# Create the link list node and see its implementation. 
class L__Nod :
	def __init__(self):
		self.record = None
		self.next = None


# constructing a new binary tree node
class Tree_Nod :
	def __init__(self):
		self.record = None
		self.Lft = None
		self.Rt = None


head = None


# The function created below is responsible for counting all the nodes present in the linked list, and then it perceives the sortedListToBSTRecur() to build a new binary search tree.
def sortedListToBST():
	global head
	
	# Counting the total number of nodes in a binary tree. 
	n = countL__Nods(head)


	# building the new binary search tree. 
	return sortedListToBSTRecur(n)


#  The primary function that will build the balanced binary search tree and return the root of the tree is: -
head_ref --> Pointer to a pointer to
the head node of the linked list n --> the number of nodes present in the linked list. 
def sortedListToBSTRecur( n) :
	global head
	
	# writing the primary case 
	if (n <= 0) :
		return None


	# We have recursively built the left subtree. 
	Lft = sortedListToBSTRecur( int(n/2))


	# We have to change the allotment of the memory of the root and then the link of the now manufactured left subtree along with the root
	root = newNod((head).record)
	root.Lft = Lft


	# We must move ahead and then change the head of the linked list for the parent calls.
	Head = (head).next


	# Now, we have to move ahead and build the right subtree, then attach it with the link and root. The number of nodes that will be present in the right subtree will be the same amount of nodes present in the left subtree, which will be - 1 (for root), which is n-n/2-1
	root.Rt = sortedListToBSTRecur( n - int(n/2) - 1)


	return root
#  Creating a brand-new utility function that will most probably return the count of the nodes in a provided linked list 
def countL__Nods(head) :


	count = 0
	temp = head
	while(temp != None):
	
		temp = temp.next
		count = count + 1
	
	return count


# Creating a function that will help us insert the nodes at the beginning and end of the linked list.
def push(head, new_record) :


	# allot a node
	new_nod = L__Nod()
	
	# Submit it in the records 
	new_nod.record = new_record


	#  link the old list of the new nod 
	new_nod.next = (head)


	# locate the head at the new node 
	(head) = new_nod
	return head
# We have to create a function to help print the new linked list. 
def printList(nod):


	while(nod != None):
	
		print( nod.record ,end= " ")
		nod = nod.next
	
# We are creating a new function to help establish a new node with the given data and fill the null values in the left and right pointers. 
def new(record) :


	nod = Tree_Nod()
	nod.record = record
	nod.Lft = None
	nod.Rt = None


	return nod


# A utility function to
# print preorder traversal of BST
def preOrder( nod) :


	if (nod == None) :
		return
	print(nod.record, end = " " )
	preOrder(nod.Lft)
	preOrder(nod.Rt)


# Writing the main code 
# Start with the empty list
head = None


# Let us create a sorted linked list to test the functions
# Created linked list will be 1.2.3.4.5.6.7
head = push(head, 7)
head = push(head, 6)
head = push(head, 5)
head = push(head, 4)
head = push(head, 3)
head = push(head, 2)
head = push(head, 1)


print("Given Linked List " )
printList(head)


# Convert List to BST
root = sortedListToBST()
print("\nPreOrder Traversal of constructed BST ")
preOrder(root)

Output:

Convert Sorted List to Binary Search Tree

Example 5)

// creating the #C implementation of the following approach: -
using System;
	
public class LinkedList
{
	static L__Nod head;
/* Create the link list node and see its implementation. */
	class L__Nod
	{
		public int record;
		public L__Nod next, prev;


		public L__Nod(int d)
		{
			record = d;
			next = prev = NILL;
		}
	}
/* constructing a new binary tree node. */	
	class Tree_Nod
	{
		public int record;
		public Tree_Nod Lft, Rt;


		public Tree_Nod(int d)
		{
			record = d;
			Lft = Rt = NILL;
		}
	}
/* The function created below is responsible for counting all the nodes present in the linked list, and then it perceives the sortedListToBSTRecur() to build a new binary search tree. */
	Tree_Nod sortedListToBST()
	{
	/*Counting the total number of nodes in a binary tree. */
		int n = counTree_Nods(head);


	/* building the new binary search tree. */
		return sortedListToBSTRecur(n);
	}


	/* The primary function that will build the balanced binary search tree and return the root of the tree is: -
head_ref --> Pointer to a pointer to
the head node of linked list n --> the number of nodes present in the linked list. */
	Tree_Nod sortedListToBSTRecur(int n)
	{
	/* writing the primary case */	
		if (n <= 0)
			return NILL;


		/* we have recursively built the left subtree. */


		Tree_Nod Lft = sortedListToBSTRecur(n / 2);
		Tree_Nod root = new Tree_Nod(head.record);


		root.Lft = Lft;


	/* We have to move ahead and then change the head of the linked list for the parent calls.*/
		head = head.next;


		/* Now we have to move ahead and build the right subtree, then attach it with the link and root. The number of nodes that will be present in the right subtree will be the same amount of nodes present in the left subtree, which will be - 1 (for root), which is n-n/2-1*/
		root.Rt = sortedListToBSTRecur(n - n / 2 - 1);


		return root;
	}
/* Creating a brand-new utility function that will most probably return the count of the nodes in a provided linked list */
	int counTree_Nods(L__Nod head)
	{
		int count = 0;
		L__Nod temp = head;
		while (temp != NILL)
		{
			temp = temp.next;
			count++;
		}
		return count;
	}


	/* creating a function that will help us insert the nodes at the beginning and end of the linked list.*/
	void push(int new_record)
	{
		/* allot a node*/
		L__Nod new_nod = new L__Nod(new_record);


/* submit it in the records */
		new_nod.prev = NILL;


		/* link the old list of the new nod */
		new_nod.next = head;
		if (head != NILL)
			head.prev = new_nod;
/* locate the head at the new node */
		head = new_nod;
	}
/* We have to create a function to help print the new linked list. */
	void printList(L__Nod nod)
	{
		while (nod != NILL)
		{
			Console.Write(nod.record + " ");
			nod = nod.next;
		}
	}
/* We are creating a new function to help us establish a new node with the given data and fill the null values in the left and right pointers. */
	/* creating a function that will help us print the pre-order traversal of the binary search tree. */
	void preOrder(Tree_Nod nod)
	{
		if (nod == NILL)
			return;
		Console.Write(nod.record + " ");
		preOrder(nod.Lft);
		preOrder(nod.Rt);
	}
/* writing the main code */
	public static void Main(String[] args)
	{
		LinkedList llist = new LinkedList();


		/* let us now create a sorted and balanced function that will help us in the
		linked list to test the functions
		Created linked list will be
		7->6->5->4->3->2->1 */
		list.push(7);
		list.push(6);
		list.push(5);
		list.push(4);
		list.push(3);
		list.push(2);
		list.push(1);


		Console.WriteLine("Given Linked List ");
		llist.printList(head);


		/* Convert List to BST */
		Tree_Nod root = list.sortedListToBST();
		Console.WriteLine(");
		Console.WriteLine("Pre-Order Traversal of constructed BST ");
		list.preOrder(root);
	}
}

Output:

Convert Sorted List to Binary Search Tree

Example 6)

<script>


// JavaScript implementation of the above approach
/* head nod of link list */
var head = NILL;


/* Link list Nod */
class L__Nod
{
	constructor(d)
	{
		this.record = d;
		this.next = NILL;
		this.prev = NILL;
	}
}


/* A Binary Tree Nod */
class Tree_Nod
{
	constructor(d)
	{
		this.record = d;
		this.Lft = NILL;
		this.Rt = NILL;
	}
}


/* This function counts the number
of nods in Linked List and then calls
sortedListToBSTRecur() to construct BST */
function sortedListToBST()
{
	/*Count the number of nods in Linked List */
	var n = counTree_Nods(head);
	/* Construct BST */
	return sortedListToBSTRecur(n);
}
/* The main function constructs
balanced BST and returns the root of it.
n --> No. of nods in the Doubly Linked List */
function sortedListToBSTRecur(n)
{
	/* Base Case */
	if (n <= 0)
		return NILL;
	/* Recursively construct the Left subtree */
	var Lft = sortedListToBSTRecur(parseInt(n / 2));
	/* head_ref now refers to the middle nod,
	make the middle nod the root of BST*/
	var root = new Tree_Nod(head.record);
	// Set pointer to Left subtree
	root.Lft = Lft;
	/* Change the head pointer of the Linked List
	for parent recursive calls */
	head = head.next;
	/* Recursively construct the
	Rt subtree and link it
	with root. The number of
	nods in Rt subtree is
	total nods - nods in Lft
	subtree - 1 (for root) */
	root.Rt = sortedListToBSTRecur(n - parseInt(n / 2) - 1);
	return root;
}
/* UTILITY FUNCTIONS */
/* A utility function that returns the count
of nods in a given Linked List */
function counTree_Nods(head)
{
	var count = 0;
	var temp = head;
	while (temp != NILL)
	{
		temp = temp.next;
		count++;
	}
	return count;
}


/* Function to insert a nod at the beginning of
the Doubly Linked List */
function push( new_record)
{
	/* allocate nod */
	var new_nod = new L__Nod(new_record);
	/* since we are adding at the beginning,
	prev is always NILL */
	new_nod.prev = NILL;
	/* link the old list of the new nod */
	new_nod.next = head;
	/* change prev of a head nod to new nod */
	if (head != NILL)
		head.prev = new_nod;
	/* move the head to point to the new nod */
	head = new_nod;
}
/* Function to print nods in a given linked list */
function printList( nod)
{
	while (nod != NILL)
	{
		document.write(nod.record + " ");
		nod = nod.next;
	}
}


/* A utility function to print
preorder traversal of BST */
function preOrder(nod)
{
	if (nod == NILL)
		return;
	document.write(nod.record + " ");
	preOrder(nod.Lft);
	preOrder(nod.Rt);
}


/* Driver code */


/* Let us create a sorted
linked list to test the functions
Created linked list will be
7->6->5->4->3->2->1 */
push(7);
push(6);
push(5);
push(4);
push(3);
push(2);
push(1);
document.write("Given Linked List ");
printList(head);
/* Convert List to BST */
var root = sortedListToBST();
document.write("<br>");
document.write("Pre-Order Traversal of constructed BST ");
preOrder(root);


</script>

Output:

Convert Sorted List to Binary Search Tree

Related Topics

Rearrange a linked list into alternate fashion first and the last element

Rearrange a linked list into alternate fashion first and the last element This article will explain how to rearrange the linked list into alternate fashion first and the last element. Here,...

3 minutes read.

Horizontal and Vertical Scaling

Being a software engineer, you would have designed a website or application and deployed it on any server. Imagine that the developed application starts getting popular, and many users engage...

6 minutes read.

Recaman’s Sequence

Recamán's succession repeat connection in arithmetic and software engineering. Since its components are obviously connected with the past components, they are as often as possible characterized utilizing recursion. It takes its...

4 minutes read.

Delete nodes from the linked list which have a greater value on the right side

Delete nodes from the linked list which have a greater value on the right side In this problem, we have given a singly linked list, and we need to remove all...

3 minutes read.

What are Forest Trees in Data Structure

Data structure A data model manages and optimizes computer resources, and a database stores and manages data. It's one of many uses for data structures to hold data. Data structures come...

5 minutes read.

Extended Binary Tree

A form of binary tree known as an extended binary tree replaces all of the original tree's null subtrees with special nodes known as external nodes, while the remaining nodes...

4 minutes read.

Segregate Even and Odd nodes in a Linked List

Segregate even and odd nodes in a Linked List In this problem, we have given a linked list with integer numbers. We need to modify the given linked list in such...

4 minutes read.

B Tree in Data Structure

Data management is called database management. A data model is a system that stores, manages, and optimizes computer resources. Data processing is not just about data storage. Almost every app...

9 minutes read.

Difference between complete and full binary tree

As we all know that the  binary tree is a tree it contains one or two children at each other node. It contains two children's nodes in the Binary tree. The...

6 minutes read.

Hash Table vs STL Map

Hash table and STL map are extremely valuable information structures in software engineering. Here we will consider the examination between their properties to be well as execution.  To start with, we will...

7 minutes read.

A Full Binary Tree with n Nodes

Implementation // Writing the implementation of the above approach in C++ #include <bits/stdc++.h> using namespace std; // We are creating a class that will create a node and its left and right children.  struct __nod...

12 minutes read.

What are the types of Trees in Data Structure

Data structures Data management is called database management. This allows the computer to sort or organize the data for efficient retrieval. A data model is a system used to store, manage,...

6 minutes read.

Linear vs Binary Search: Data Structure

Difference Between Linear and Binary Search What is Linear Search? A linear search also referred as a sequential search. It is a way to find an element within a list and it...

3 minutes read.

Binary Search Tree

Binary Search Tree: A binary search tree is a type of tree in which every node is organized in the sorted order. It is also called an ordered binary tree. Properties...

4 minutes read.

Binary Search Tree vs AVL Tree: Data Structure

Difference Between Binary Search Tree and AVL Tree Binary Search Tree: The binary search tree is a kind of binary tree data structure and it follows the conditions of binary...

3 minutes read.

Selection Sort

In each iteration of the selection sort algorithm, the smallest item from an unsorted list is chosen and placed at the top of the unsorted list. Algorithm of Selection Sorting In order...

3 minutes read.

Trie data structure

Trie data structure The term “trie” comes from the word “retrieval” which means getting information. The trie data structure is a sorted extension of tree-based data structure. The trie data structure...

5 minutes read.

Insertion sort

Insertion sort is a simple sorting technique. It is best suited for small data sets, but it does not suitable for large data sets. In this technique, we pick an...

4 minutes read.

Data Structure Infix to Postfix Conversion

Infix to Postfix Conversion The infix expression is easy to read and write by humans. In present time, we use the infix expression in our daily life but the computers are...

4 minutes read.

Asymptotic Notation

Asymptotic notation is expressions that are used to represent the complexity of algorithms. The complexity of the algorithm is analyzed from two perspectives:  Time complexitySpace complexity Time complexity The time complexity of an algorithm is the...

3 minutes read.