Construct a complete binary tree from its linked list representation
Given a linked list, construct a complete binary tree from it. Assume that the order of elements present in the linked list is the same as that in the complete tree’s array representation.
For a tree node at position i in the linked list, the left child is present at position 2×i, and the right child is present at position 2×i + 1. (Here, position i starts from 1).
For example, the linked list 1 —> 2 —> 3 —> 4 —> 5 —> 6 should be converted into the following complete binary tree:
/ \
2 3
/ \ /
4 5 6
Unlike an array, we cannot directly access nodes in the linked list. Therefore, it’s not possible to recursively construct a complete binary tree with a linked list.
Note that the root of the complete binary tree is the head of the linked list and its two children are the next two nodes in the linked list, and each level in a complete binary tree contains consecutive nodes in the linked list.
We know that each level in a complete binary tree is filled except possibly the last, where the nodes are filled from left to right. The idea is to build the complete binary tree level-by-level. Following is a pseudocode for a simple queue-based algorithm using level order traversal:
root —> next_node(head)
q —> empty queue
q.enqueue(root)
while (next_node(head))
node —> q.dequeue()
node.left = next_node(head)
q.enqueue(node.left)
node.right = next_node(head)
q.enqueue(node.right)
The algorithm can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
#include <iostream> #include <queue> using namespace std; // A Binary Tree Node struct TreeNode { int data; TreeNode *left, *right; TreeNode(int data) { this->data = data; this->left = this->right = nullptr; } }; // A Linked List Node struct ListNode { int data; ListNode* next; ListNode(int data) { this->data = data; this->next = nullptr; } }; // Utility function to create a new node with the given data and // pushes it onto the list's front ListNode* push(ListNode* head, int data) { ListNode* node = new ListNode(data); node->next = head; head = node; return head; } // Function to perform preorder traversal on a given binary tree. void preorder(TreeNode* root) { if (root == nullptr) { return; } cout << root->data << ' '; preorder(root->left); preorder(root->right); } // Function to construct a complete binary tree from a given linked list TreeNode* convertListToBinaryTree(ListNode* head) { // base case if (head == nullptr) { return nullptr; } // create the root using the first node of the linked list TreeNode* root = new TreeNode(head->data); // move the head pointer to the next node head = head->next; // create a queue to store tree pointers and enqueue the root node queue<TreeNode*> q; q.push(root); // loop till the end of the linked list is reached while (head) { // dequeue front node TreeNode* front = q.front(); q.pop(); // create a left child from the next node in the linked list and enqueue it front->left = new TreeNode(head->data); q.push(front->left); // move the head pointer to the next node head = head->next; // if the linked list did not reach its end if (head != nullptr) { // create the right child from the next node in the linked list and // enqueue it front->right = new TreeNode(head->data); q.push(front->right); // move the head pointer to the next node head = head->next; } } // return root of the constructed binary tree return root; } int main() { ListNode* head = nullptr; int n = 6; // construct a linked list for (int i = n; i > 0; i--) { head = push(head, i); } TreeNode* root = convertListToBinaryTree(head); preorder(root); return 0; } |
Output:
1 2 4 5 3 6
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 |
import java.util.ArrayDeque; import java.util.Queue; // A Binary Tree Node class TreeNode { int data; TreeNode left, right; TreeNode(int data) { this.data = data; this.left = this.right = null; } } // A Linked List Node class ListNode { int data; ListNode next; ListNode(int data) { this.data = data; this.next = null; } } class Main { // Utility function to create a new node with the given data and // pushes it onto the list's front public static ListNode push(ListNode head, int data) { ListNode node = new ListNode(data); node.next = head; node.data = data; return node; } // Function to perform preorder traversal on a given binary tree. public static void preorder(TreeNode root) { if (root == null) { return; } System.out.print(root.data + " "); preorder(root.left); preorder(root.right); } // Function to construct a complete binary tree from a given linked list public static TreeNode convertListToBinaryTree(ListNode head) { // base case if (head == null) { return null; } // create the root using the first node of the linked list TreeNode root = new TreeNode(head.data); // move the head pointer to the next node head = head.next; // create a queue to store tree pointers and enqueue the root node Queue<TreeNode> q = new ArrayDeque<>(); q.add(root); // loop till the end of the linked list is reached while (head != null) { // dequeue front node TreeNode front = q.poll(); // create a left child from the next node in the linked list and enqueue it front.left = new TreeNode(head.data); q.add(front.left); // move the head pointer to the next node head = head.next; // if the linked list did not reach its end if (head != null) { // create the right child from the next node in the linked list and // enqueue it front.right = new TreeNode(head.data); q.add(front.right); // move the head pointer to the next node head = head.next; } } // return root of the constructed binary tree return root; } public static void main(String[] args) { ListNode head = null; int n = 6; // construct a linked list for (int i = n; i > 0; i--) { head = push(head, i); } TreeNode root = convertListToBinaryTree(head); preorder(root); } } |
Output:
1 2 4 5 3 6
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
from collections import deque # A Binary Tree Node class TreeNode: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # A Linked List Node class ListNode: def __init__(self, data, next=None): self.data = data self.next = next # Function to perform preorder traversal on a given binary tree. def preorder(root): if root is None: return print(root.data, end=' ') preorder(root.left) preorder(root.right) # Function to construct a complete binary tree from a given linked list def convertListToBinaryTree(head): # base case if head is None: return None # create the root using the first node of the linked list root = TreeNode(head.data) # move the head pointer to the next node head = head.next # create a queue to store tree pointers and enqueue the root node q = deque() q.append(root) # loop till the end of the linked list is reached while head: # dequeue front node front = q.popleft() # create a left child from the next node in the linked list and enqueue it front.left = TreeNode(head.data) q.append(front.left) # move the head pointer to the next node head = head.next # if the linked list did not reach its end if head: # create the right child from the next node in the linked list and # enqueue it front.right = TreeNode(head.data) q.append(front.right) # move the head pointer to the next node head = head.next # return root of the constructed binary tree return root if __name__ == '__main__': head = None n = 6 # construct a linked list for i in reversed(range(1, n + 1)): head = ListNode(i, head) root = convertListToBinaryTree(head) preorder(root) |
Output:
1 2 4 5 3 6
The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the total number of nodes in the linked list.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)