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:
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:
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:
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:
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:
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:
