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

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.