Trusted answers to developer questions

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

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.

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

Related Courses