Convert Heap ordered Linked List to Binary Tree

Problem

Convert heap ordered linked list to binary tree.

Examples

Example 1: If we are given a linked list that contains nodes in heap order such as 1 -> 4 -> 5 -> 6 -> 8 -> 10 -> 11-> null then we want to convert it to a balanced binary tree as follows -

Input: head = [3 -> 2 -> 1 -> 4 -> 5 -> null]

Output: 
      3
     / \
    2   1
   / \
  4   5
 


Explanation:
The queue-based approach creates the binary tree level by level:
- Add 1 to the queue as the root.
- Dequeue 1, attach 2 (left) and 3 (right), and enqueue both.
- Dequeue 2, attach 4 (left) and 5 (right), and enqueue them.

Solution

To solve the problem of converting a linked list representation of a heap into a binary tree (BT), we can follow the straightforward approach of constructing the binary tree level by level based on the heap properties stored in the linked list.

In a heap (especially a complete binary heap), nodes at position i in the array have:

• Left child at 2*i + 1.
• Right child at 2*i + 2.

Method 1 - Using list indices

Here is the approach:

• A linked list where each node contains a value of the heap. Each node also has a next pointer pointing to the next node in the list.
• As the linked list represents a complete heap, iteratively construct the binary tree by mapping:
  • Linked list nodes to tree nodes using heap indices.

Code

Java

class Solution {
    public TreeNode convertToBT(ListNode head) {
        if (head == null) return null;

        // Step 1: Convert LinkedList to Array of TreeNode
        List<TreeNode> nodes = new ArrayList<>();
        while (head != null) {
            nodes.add(new TreeNode(head.val));
            head = head.next;
        }

        // Step 2: Link nodes to mimic binary tree structure (heap-like linkage)
        for (int i = 0; i < nodes.size(); i++) {
            if (2 * i + 1 < nodes.size()) {  // Left Child index
                nodes.get(i).left = nodes.get(2 * i + 1);
            }
            if (2 * i + 2 < nodes.size()) {  // Right Child index
                nodes.get(i).right = nodes.get(2 * i + 2);
            }
        }
        
        return nodes.get(0);  // Root of the binary tree
    }
}

Python

class Solution:
    def convert_to_bt(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head:
            return None
        
        # Step 1: Convert Linked List to Array of TreeNode
        nodes = []  # Array to hold TreeNode objects
        while head:
            nodes.append(TreeNode(head.val))
            head = head.next
        
        # Step 2: Link nodes to mimic binary tree structure (heap-like linkage)
        for i in range(len(nodes)):
            if 2 * i + 1 < len(nodes):  # Left Child index
                nodes[i].left = nodes[2 * i + 1]
            if 2 * i + 2 < len(nodes):  # Right Child index
                nodes[i].right = nodes[2 * i + 2]
        
        return nodes[0]  # Root of the binary tree

Complexity

• ⏰ Time complexity: O(n), where n is the number of elements in the linked list — we traverse the list once and link nodes in constant time per node
• 🧺 Space complexity: O(n) for using the list to create result.

Method 2 - Using the queue

Using a queue is a great technique for level-order traversal and is perfectly suited to create a binary tree from the linked list representation of a heap.

Approach

1. Read all the ListNodes from the linked list and convert them into corresponding TreeNodes.
2. Use a queue to maintain the parent-child relationship while constructing the binary tree:
   • Initially, enqueue the root node (first node of the linked list).
   • Dequeue the parent node, then:
     • Attach the next TreeNode from the list as its left child (if available). Enqueue this child.
     • Attach the next TreeNode as its right child (if available). Enqueue this child.
3. Repeat until the binary tree is constructed.

Code

Java

class Solution {
    public TreeNode convertToBT(ListNode head) {
        if (head == null) return null;

        // Create the root node from the first linked list node
        TreeNode root = new TreeNode(head.val);
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root); // Queue for level-order construction
        head = head.next; // Move to the next node in the linked list

        // Construct the binary tree using the queue
        while (head != null) {
            TreeNode parent = queue.poll(); // Get parent node from the queue

            // Create left child if available
            TreeNode leftChild = new TreeNode(head.val);
            parent.left = leftChild;
            queue.add(leftChild);
            head = head.next;

            // Create right child if available
            if (head != null) {
                TreeNode rightChild = new TreeNode(head.val);
                parent.right = rightChild;
                queue.add(rightChild);
                head = head.next;
            }
        }

        return root;
    }
}

Python

class Solution:
    def convert_to_bt(self, head: Optional[ListNode]) -> Optional[TreeNode]:
        if not head:
            return None
        
        # Create the root node from the first linked list node
        root = TreeNode(head.val)
        queue = deque([root])  # Queue for level-order construction
        head = head.next  # Move to the next node in the linked list
        
        # Construct the binary tree using the queue
        while head:
            parent = queue.popleft()  # Get parent node
            
            # Create left child if available
            left_child = TreeNode(head.val)
            parent.left = left_child
            queue.append(left_child)
            head = head.next
            
            # Create right child if available
            if head:  # Ensure there's still a node left
                right_child = TreeNode(head.val)
                parent.right = right_child
                queue.append(right_child)
                head = head.next
        
        return root

Complexity

• ⏰ Time complexity: O(n), where n is the number of elements in the linked list — we traverse the list once and link nodes in constant time per node
• 🧺 Space complexity: O(n) for using the queue to create result.