Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

how
convert
sorted list
binary tree

How to convert a sorted list to a binary tree

Educative Answers Team

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)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.

The linked list:

%0 node_1 1 node_1564744979451 2 node_1->node_1564744979451 node_1564744912919 3 node_1564744979451->node_1564744912919 node_1564744945966 4 node_1564744912919->node_1564744945966 node_1564744901302 5 node_1564744945966->node_1564744901302 node_1564745552214 6 node_1564744901302->node_1564745552214 node_1564745474095 7 node_1564745552214->node_1564745474095

The converted binary tree:

%0 node_1 4 node_1564745454796 2 node_1->node_1564745454796 node_1564745453945 6 node_1->node_1564745453945 node_1564745513249 1 node_1564745454796->node_1564745513249 node_1564745544123 3 node_1564745454796->node_1564745544123 node_1564745511471 5 node_1564745453945->node_1564745511471 node_1564745469108 7 node_1564745453945->node_1564745469108

Implementation

The code below implements the method above.

#include <iostream> 
using namespace std; 
  
/* Link list node */
class listNode  
{  
    public: 
    int data;  
    listNode* next;  
};  
  
/* A Binary Tree node */
class treeNode  
{  
    public: 
    int data;  
    treeNode* left;  
    treeNode* right;  
};  
  
treeNode* newNode(int data);  
int countNodesOfList(listNode *head);  
treeNode* sortedListToBTrecur(listNode **head_ref, int n);  
  
  
/* This function counts the number of  
nodes in Linked List and then calls*/  

treeNode* sortedListToBST(listNode *head)  
{  
    /*Count the number of nodes in Linked List */
    int n = countNodesOfList(head);  
  
    return sortedListToBTrecur(&head, n);  
}  
  
/* The main function that constructs  
balanced BT and returns root of it.  
head_ref --> Pointer to pointer to  
head node of linked list n --> No. 
of nodes in Linked List */
treeNode* sortedListToBTrecur(listNode **head_ref, int n)  
{  
    /* Base Case */
    if (n <= 0)  
        return NULL;  
  
    /* Recursively construct the left subtree */
    treeNode *left = sortedListToBTrecur(head_ref, n/2);  
  
    /* Allocate memory for root, and  
    link the above constructed left  
    subtree with root */
    treeNode *root = newNode((*head_ref)->data);  
    root->left = left;  
  
    /* Change head pointer of Linked List 
    for parent recursive calls */
    *head_ref = (*head_ref)->next;  
  
    /* 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 countNodesOfList(listNode *head)  
{  
    int count = 0;  
    listNode *temp = head;  
    while(temp)  
    {  
        temp = temp->next;  
        count++;  
    }  
    return count;  
}  
  
/* Function to insert a node  
at the beginning of the linked list */
void push(listNode** head_ref, int new_data)  
{  
    /* allocate node */
    listNode* new_node = new listNode(); 
      
    /* put in the data */
    new_node->data = new_data;  
  
    /* link the old list off the new node */
    new_node->next = (*head_ref);  
  
    /* move the head to point to the new node */
    (*head_ref) = 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()  
{  
    /* Start with the empty list */
    listNode* head = NULL;  
  
    /* 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<<"The initial linked list was :";  
    printList(head);  
  
    /* Convert List to BT */
    treeNode *root = sortedListToBST(head);  
    cout<<"\nTraversal of the BT from the Root to the leaves : ";  
    preOrder(root);  
  
    return 0;  
}  

RELATED TAGS

how
convert
sorted list
binary tree
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring