Posted on by Kalkicode
Code Binary Tree

# Inplace construct linked list into complete binary tree

In computer science, trees are a fundamental data structure with numerous applications, including binary trees. Binary trees have many variants, one of which is the complete binary tree. A complete binary tree is a binary tree in which every level of the tree is completely filled, except possibly for the last level, which is filled from left to right. In this article, we'll explore how to construct a complete binary tree from a given linked list.

## Problem Statement

Given a singly linked list, the task is to convert it into a complete binary tree inplace. The goal is to efficiently reorganize the elements of the linked list into a binary tree structure that satisfies the properties of a complete binary tree.

## Description

Imagine you have a singly linked list like this:

``1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> NULL``

Your goal is to transform this linked list into a complete binary tree such that it looks like this:

``````            1
/ \
/   \
/     \
2       3
/ \     / \
/   \   /   \
4     5 6     7
/ \   /
8   9 10``````

## Idea to Solve the Problem

To solve this problem efficiently, we can use a recursive approach. The basic idea is to start with the linked list, find the middle node, and make it the root of the binary tree. Then, recursively apply the same process to the left and right halves of the linked list. This approach ensures that the binary tree is constructed in a complete manner, with the left subtree containing the smaller values and the right subtree containing the larger values.

## Pseudocode

Here is a pseudocode representation of the algorithm to construct the complete binary tree from a linked list:

``````function convertLinkedListToBinaryTree(head):
return null

// Find the middle of the linked list

// Create a binary tree node with the middle element
root = new TreeNode(mid.data)

// Recursively construct the left and right subtrees

return root``````

## Algorithm Explanation

1. The `convertLinkedListToBinaryTree` function takes the head of the linked list as input.

2. If the head is null, it returns null, indicating an empty subtree.

3. The `findMiddle` function is called to find the middle node of the linked list. This is done using the slow and fast pointer technique, where the slow pointer moves one step at a time and the fast pointer moves two steps at a time until the fast pointer reaches the end of the list. The slow pointer will then be at the middle of the list.

4. A new binary tree node `root` is created with the data from the middle node.

5. Recursively, the left and right subtrees are constructed by calling `convertLinkedListToBinaryTree` on the left half of the linked list (up to the middle node) and on the right half of the linked list (starting from the node after the middle node).

6. The left and right subtrees are attached to the `root`.

7. The `root` of the binary tree is returned.

## Resultant Output Explanation

After implementing the above algorithm, you will have successfully converted the given linked list into a complete binary tree. The output will be in the form of three traversals: preorder, inorder, and postorder.

• Preorder Traversal

This traversal visits the root node first, then the left subtree, and finally the right subtree. It will display the elements of the binary tree in the order they were constructed.

• Inorder Traversal

This traversal visits the left subtree first, then the root node, and finally the right subtree. It will display the elements of the binary tree in ascending order, as it represents a binary search tree.

• Postorder Traversal

This traversal visits the left subtree first, then the right subtree, and finally the root node. It will display the elements of the binary tree in a way that can be used to delete nodes from the tree.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post