Related Tags

how
convert
sorted list
binary tree

How to convert a sorted list to a binary tree

A sorted linked list is used to construct a binary tree from the leaves to the root. The idea is to insert nodes in a binary tree in the same order as they appear in the linked list so that the tree can be constructed with the time complexity of $O(n)$.

Method

The number of nodes in the linked list are counted and set equal to n. First, the middle node is set as the root (always). Then, the left subtree is constructed recursively, using the left n/2 nodes, and connected with the root at the end. The right subtree is similarly constructed and connected to the root.

While constructing the BST, we ​keep moving the list head pointer to the next node so that we have the appropriate pointer in each recursive call.

Example

Suppose the following linked list needs to be converted into a binary tree. The following illustrations make use of the above-mentioned method to create a binary tree.

Implementation

The code below implements the method above.

#include <iostream>
using namespace std;

class listNode
{
public:
int data;
listNode* next;
};

/* A Binary Tree node */
class treeNode
{
public:
int data;
treeNode* left;
treeNode* right;
};

treeNode* newNode(int data);

/* This function counts the number of
nodes in Linked List and then calls*/

{
/*Count the number of nodes in Linked List */

}

/* The main function that constructs
balanced BT and returns root of it.
head_ref --> Pointer to pointer to
of nodes in Linked List */
{
/* Base Case */
if (n <= 0)
return NULL;

/* Recursively construct the left subtree */

/* Allocate memory for root, and
subtree with root */
root->left = left;

for parent recursive calls */

/* Recursively construct the right
subtree and link it with root
The number of nodes in right subtree
is total nodes - nodes in
left subtree - 1 (for root) which is n-n/2-1*/
root->right = sortedListToBTrecur(head_ref, n - n / 2 - 1);

return root;
}

/* A utility function that returns
count of nodes in a given Linked List */
{
int count = 0;
while(temp)
{
temp = temp->next;
count++;
}
return count;
}

/* Function to insert a node
at the beginning of the linked list */
{
/* allocate node */
listNode* new_node = new listNode();

/* put in the data */
new_node->data = new_data;

/* link the old list off the new node */

/* move the head to point to the new node */
}

/* Function to print nodes in a given linked list */
void printList(listNode *node)
{
while(node!=NULL)
{
cout << node->data << " ";
node = node->next;
}
}

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
treeNode* newNode(int data)
{
treeNode* node = new treeNode();
node->data = data;
node->left = NULL;
node->right = NULL;

return node;
}

/* A utility function to
print preorder traversal of BT */
void preOrder(treeNode* node)
{
if (node == NULL)
return;
cout<<node->data<<" ";
preOrder(node->left);
preOrder(node->right);
}

/* Driver code*/
int main()
{

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

cout<<"The initial linked list was :";

/* Convert List to BT */
cout<<"\nTraversal of the BT from the Root to the leaves : ";
preOrder(root);

return 0;
}  

RELATED TAGS

how
convert
sorted list
binary tree
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time