Construct Complete Binary Tree from its Linked List Representation
Given Linked List Representation of Complete Binary Tree, construct the Binary tree. A complete binary tree can be represented in an array in the following approach.
If root node is stored at index i, its left, and right children are stored at indices 2*i+1, 2*i+2 respectively.
Suppose tree is represented by a linked list in same way, how do we convert this into normal linked representation of binary tree where every node has data, left and right pointers? In the linked list representation, we cannot directly access the children of the current node unless we traverse the list.
Q. Program to implement Binary Tree using the linked list
Explanation
In this program, we need to create the binary tree by inserting nodes and displaying nodes in inorder fashion. A typical binary tree can be represented as follows:
In the binary tree, each node can have at most two children. Each node can have zero, one or two children. Each node in the binary tree contains the following information:
Data that represents value stored in the node.
Left that represents the pointer to the left child.
Right that represents the pointer to the right child.
Algorithm
- Define Node class which has three attributes namely: data left and right. Here, left represents the left child of the node and right represents the right child of the node.
- When a node is created, data will pass to data attribute of the node and both left and right will be set to null.
- Define another class which has an attribute root.
- Root represents the root node of the tree and initialize it to null.
- insert[] will add a new node to the tree:
- It checks whether the root is null, which means the tree is empty. It will add the new node as root.
- Else, it will add root to the queue.
- The variable node represents the current node.
- First, it checks whether a node has a left and right child. If yes, it will add both nodes to queue.
- If the left child is not present, it will add the new node as the left child.
- If the left is present, then it will add the new node as the right child.
- Inorder[] will display nodes of the tree in inorder fashion.
- It traverses the entire tree then prints out left child followed by root then followed by the right child.
Solution
Python
Output:
Binary tree after insertion 1 Binary tree after insertion 2 1 3 Binary tree after insertion 4 2 5 1 3 Binary tree after insertion 4 2 5 1 6 3 7
C
Output:
Binary tree after insertion 1 Binary tree after insertion 2 1 3 Binary tree after insertion 4 2 5 1 3 Binary tree after insertion 4 2 5 1 6 3 7
JAVA
Output:
Binary tree after insertion 1 Binary tree after insertion 2 1 3 Binary tree after insertion 4 2 5 1 3 Binary tree after insertion 4 2 5 1 6 3 7
C#
Output:
Binary tree after insertion 1 Binary tree after insertion 2 1 3 Binary tree after insertion 4 2 5 1 3 Binary tree after insertion 4 2 5 1 6 3 7
PHP
Output:
Binary tree after insertion 1 Binary tree after insertion 2 1 3 Binary tree after insertion 4 2 5 1 3 Binary tree after insertion 4 2 5 1 6 3 7
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 #include 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 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 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; } |
DownloadRun Code
Output:
1 2 4 5 3 6
Example
Input
1 -> 2 -> 3 -> 4 -> 5
Output
In-order traversal
4 2 5 1 3
Pin
Algorithm for Construct Complete Binary Tree
A complete binary tree is a binary tree that has all the levels completely filled except for the last level and all the nodes in the last level are as left as possible. Also, when a complete tree is represented through an array a node at index i in the array has its left child at index [2 * i + 1] and right child at index [2 * i + 2]. We can visualize the same thing in the linked list representation.
So the children of node at index 0 are present at index 1 and 2, children of node at index 1 are present at index 3 and 4, and so on.
The idea to convert the linked list representation to the tree is that the first node of the linked list is always the root of the tree. So we push the root in a queue, we do a BFS on the tree and simultaneously traverse in the linked list to convert it into the tree. For every node in the tree, we traverse two nodes in the linked list, one for the left child and one for the right child.
- Create a queue, say q.
- Push the head of the linked list to the queue.
- While the end of the linked list is not reached, repeat step 4.
- Remove a node from the queue, let it be the parent. Traverse in the list, the first node is the left child of the parent, and second node is the right child of the parent. Also, enqueue the left and right child to the queue.
See also
Binary Search Tree
1. Introduction
In this tutorial, we'll cover the implementation of a binary tree in Java.
For the sake of this tutorial, we'll use a sorted binary tree that contains int values.