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](https://www.educative.io/answers/what-is-bigo-notation) 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.


## The linked list:

# 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;  
}  

class LinkedList { 
  
    /* head node of link list */
    static listNode head; 
      
    /* Link list Node */
    class listNode  
    { 
        int data; 
        listNode next, prev; 
  
        listNode(int d)  
        { 
            data = d; 
            next = prev = null; 
        } 
    } 
      
    /* A Binary Tree Node */
    class treeNode  
    { 
        int data; 
        treeNode left, right; 
  
        treeNode(int d)  
        { 
            data = d; 
            left = right = null; 
        } 
    } 
  
    /* This function counts the number of nodes in Linked List 
       and then calls sortedListToBTRecur() to construct BT */
    treeNode sortedListToBT()  
    { 
        /*Count the number of nodes in Linked List */
        int n = countNodes(head); 
  
        /* Construct BT */
        return sortedListToBTRecur(n); 
    } 
  
    /* The main function that constructs balanced BT and 
       returns root of it. 
       n  --> No. of nodes in the Doubly Linked List */
    treeNode sortedListToBTRecur(int n)  
    { 
        /* Base Case */
        if (n <= 0)  
            return null; 
  
        /* Recursively construct the left subtree */
        treeNode left = sortedListToBTRecur(n / 2); 
  
        /* head_ref now refers to middle node,  
           make middle node as root of BT*/
        treeNode root = new treeNode(head.data); 
  
        // Set pointer to left subtree 
        root.left = left; 
  
        /* Change head pointer of Linked List for parent  
           recursive calls */
        head = head.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) */
        root.right = sortedListToBTRecur(n - n / 2 - 1); 
  
        return root; 
    } 
  
    /* UTILITY FUNCTIONS */
    /* A utility function that returns count of nodes in a  
       given Linked List */
    int countNodes(listNode head)  
    { 
        int count = 0; 
        listNode temp = head; 
        while (temp != null) 
        { 
            temp = temp.next; 
            count++; 
        } 
        return count; 
    } 
  
    /* Function to insert a node at the beginging of  
       the Doubly Linked List */
    void push(int new_data)  
    { 
        /* allocate node */
        listNode new_node = new listNode(new_data); 
  
        /* since we are adding at the begining, 
           prev is always NULL */
        new_node.prev = null; 
  
        /* link the old list off the new node */
        new_node.next = head; 
  
        /* change prev of head node to new node */
        if (head != null) 
            head.prev = new_node; 
  
        /* move the head to point to the new node */
        head = new_node; 
    } 
  
    /* Function to print nodes in a given linked list */
    void printList(listNode node)  
    { 
        while (node != null)  
        { 
            System.out.print(node.data + " "); 
            node = node.next; 
        } 
    } 
  
    /* A utility function to print preorder traversal of BT */
    void preOrder(treeNode node)  
    { 
        if (node == null) 
            return; 
        System.out.print(node.data + " "); 
        preOrder(node.left); 
        preOrder(node.right); 
    } 
  
    /* Driver program to test above functions */
    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 */
        llist.push(7); 
        llist.push(6); 
        llist.push(5); 
        llist.push(4); 
        llist.push(3); 
        llist.push(2); 
        llist.push(1); 
  
        System.out.println("The initial linked list was : "); 
        llist.printList(head); 
  
        /* Convert List to BT */
        treeNode root = llist.sortedListToBT(); 
        System.out.println(""); 
        System.out.println("Traversal of the BT from the Root to the leaves : "); 
        llist.preOrder(root); 
    } 
} 

Java

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

How to convert a sorted list to a binary tree

Method

Example

The linked list:

The converted binary tree:

Implementation