💡 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.
♥️ Info: Are you AI curious but you still have to create real impactful projects? Join our official AI builder club on Skool (only $5): SHIP! - One Project Per Month
Here’s an example:
class Node:
def __init__(self, value=None):
self.value = value
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def level_order_to_linkedlist(root):
if not root:
return
q = [root]
linked_list = LinkedList()
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)
linked_list.head = dummy.next
return linked_list
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)
def convert_to_linkedlist(root):
levels = []
dfs_with_level(root, 0, levels)
linked_list = LinkedList()
dummy = current = Node(0)
for level_head in levels:
current.next = level_head
while current.next:
current = current.next
linked_list.head = dummy.next
return linked_list
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):
stack, current, linked_list = [], root, LinkedList()
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
linked_list.head = dummy.next
return linked_list
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
def level_order_to_linkedlist_deque(root):
if not root:
return
q = deque([root])
linked_list = LinkedList()
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)
linked_list.head = dummy.next
return linked_list
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
def level_order_to_linkedlist_oneliner(root):
linked_list, current = LinkedList(), Node(0)
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
linked_list.head = dummy.next.next
return linked_list
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.