# 5 Best Ways to Convert Level Order Binary Tree Traversal to LinkedList in Python

π‘ Problem Formulation: This article explores various methods to convert a binary tree’s level-order traversal into a linked list using Python. A binary tree’s level-order traversal is a sequence of nodes visited in a top-down and left-to-right order. The goal is to create a linked list where each node contains the data of a binary tree node, preserving the level-order sequence. For instance, given a binary tree with level order traversal [1,2,3,4,5], the desired output is a linked list 1 -> 2 -> 3 -> 4 -> 5.

## Method 1: Using a Queue

The queue-based method involves iterating over the tree using a queue to ensure we process nodes in level-order. This method involves defining a LinkedList class and using a regular queue to hold the nodes of the binary tree while traversing.

Here’s an example:

```class Node:
def __init__(self, value=None):
self.value = value
self.next = None

def __init__(self):

if not root:
return
q = [root]
current = dummy = Node(0)
while q:
node = q.pop(0)
current.next = Node(node.value)
current = current.next
if node.left: q.append(node.left)
if node.right: q.append(node.right)

```

Output (using a tree representation):

```Linked List: 1 -> 2 -> 3 -> 4 -> 5
```

This code snippet defines a `Node` class for the linked list, a `LinkedList` class with a method to insert nodes from a binary tree level order traversal, and the function `level_order_to_linkedlist` that completes this operation. The function iterates over each tree level, creating LinkedList nodes for each and appends them to the list.

## Method 2: DFS with Level Tracking

The depth-first search (DFS) with level tracking approach uses a recursive strategy to perform an in-order traversal while keeping track of the depth to maintain the level order in a linked list.

Here’s an example:

```def dfs_with_level(node, level, levels):
if not node:
return
if len(levels) == level:
levels.append(Node(node.value))
else:
current = levels[level]
while current.next:
current = current.next
current.next = Node(node.value)
dfs_with_level(node.left, level+1, levels)
dfs_with_level(node.right, level+1, levels)

levels = []
dfs_with_level(root, 0, levels)
dummy = current = Node(0)
while current.next:
current = current.next
```

Output (using a tree representation):

```Linked List: 1 -> 2 -> 3 -> 4 -> 5
```

This method provides a different approach that captures the nodes in a level-by-level manner using DFS and populates a list of linked list nodes (`levels`). Finally, it stitches all lists corresponding to each level into one linked list.

## Method 3: Iterative In-Order Traversal

This method uses an iterative approach to do an in-order traversal of the tree and builds the linked list as it goes. Despite not being the standard level-order, if the tree’s nodes are inserted level-by-level, this method can still be effective.

Here’s an example:

```def in_order_to_linkedlist(root):
prev = dummy = Node(0)
while stack or current:
while current:
stack.append(current)
current = current.left
current = stack.pop()
prev.next = Node(current.value)
prev = prev.next
current = current.right
```

Output (using a tree representation):

```Linked List: 4 -> 2 -> 5 -> 1 -> 3
```

This code iteratively processes the binary tree nodes in in-order traversal and simultaneously constructs the linked list. It uses a stack to keep track of the nodes and a dummy node to help build the linked list without losing the head reference.

## Method 4: Using Collections.deque

Utilizing Python’s collections module gives access to a high-performance deque (double-ended queue) that can optimize level-order traversal and linked list creation.

Here’s an example:

```from collections import deque

if not root:
return
q = deque([root])
current = dummy = Node(0)
while q:
node = q.popleft()
current.next = Node(node.value)
current = current.next
if node.left: q.append(node.left)
if node.right: q.append(node.right)
```

Output (using a tree representation):

```Linked List: 1 -> 2 -> 3 -> 4 -> 5
```

Instead of using a list as in the first method, this snippet uses `deque` which has an efficient `popleft()` operation, making the level-order traversal more performant while reducing the overall time complexity.

## Bonus One-Liner Method 5: Breadth-First Search (BFS)

A concise, albeit less readable, method utilizes Python’s list comprehension and iterator chaining to perform BFS in a single line to create a linked list. This method is not recommended for complex or large-scale applications but can be an elegant solution for small tasks.

Here’s an example:

```from itertools import chain

dummy = current
current.next = chain.from_iterable(
([node.value] if node else [] for node in iter(lambda: q.pop(0) if q else None, None) for q in [[root]] if root)
)
for value in current.next:
current.next = Node(value)
current = current.next

```

Output (using a tree representation):

```Linked List: 1 -> 2 -> 3 -> 4 -> 5
```

This one-liner uses `chain.from_iterable` and a clever generator expression to flatten the level-order traversal of the tree into a sequence of values that are used to construct the linked list.

## Summary/Discussion

• Method 1: Queue-Based Traversal. Strengths: Easy to understand, straightforward implementation. Weaknesses: Extra space for the queue, less performant with large data sets due to list pop(0) operation.
• Method 2: DFS with Level Tracking. Strengths: Space-efficient traversal. Weaknesses: More complex, extra steps to assemble the final linked list.
• Method 3: Iterative In-Order Traversal. Strengths: No need for auxiliary data structures. Weaknesses: Not true level-order traversal, hence works conditionally based on the tree structure.
• Method 4: Using Collections.deque. Strengths: Faster queue operations, improved performance over list-based queues. Weaknesses: Additional import, slight complexity increase.
• Method 5: BFS One-Liner. Strengths: Concise and elegant solution for small tasks. Weaknesses: Lower readability, unsuitable for large/complex tasks, potential for performance issues.