5 Best Ways to Convert Linked List to Zig Zag Binary Tree in Python

Rate this post

πŸ’‘ Problem Formulation: This article provides solutions for converting a linear data structure, such as a linked list, into a hierarchical one, like a zig-zag (or “zigzag”) binary tree. A zig zag binary tree is a binary tree where the first child is on the right for the first level, on the left for the next level, and alternating thereafter. Given an input linked list 1->2->3->4->5->6, the desired output is a binary tree where nodes are placed in a zigzag level order, i.e., root at level 0, 2 as a left child of 1 at level 1, 3 as a right child of 2 at level 2, and so on.

Method 1: Recursive Definition

This method involves recursively converting segments of the linked list into subtrees of the binary tree. For the zigzag pattern, we alternate between attaching the next node in the list as a left or right child in different levels of recursion. This approach allows for a clear logical flow that simulates the process of tree construction. Function specification might involve a helper function that takes in the current node in the linked list, the current depth, and a flag to indicate the direction of attachment for the next node.

Here’s an example:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def convert_to_zigzag(root, depth=0, is_right=True):
    if not root:
        return None
    binary_node = TreeNode(root.val)
    if is_right:
        binary_node.right = convert_to_zigzag(root.next, depth + 1, not is_right)
    else:
        binary_node.left = convert_to_zigzag(root.next, depth + 1, not is_right)
    return binary_node

# Example Usage
linked_list = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6))))))
binary_tree_root = convert_to_zigzag(linked_list)

The output of this code snippet would be a binary tree with a zigzag level ordering originating from the given linked list.

This example first defines a ListNode class for the linked list and a TreeNode class for the binary tree node. The convert_to_zigzag function takes the current node of the list, the depth to determine the zigzag level order, and a boolean flag to indicate the direction of child attachment. The code snippet applies this function to the example linked list to generate the corresponding binary tree.

Method 2: Iterative Level-Building

In this method, we iteratively create each level of the binary tree using a queue. At each level, we dequeue nodes and ‘wire’ children according to the current zigzag pattern. To alternate between left and right attachments across levels, we can use a variable that keeps track of the current direction. This approach is non-recursive and can be more space-efficient.

Here’s an example:

from collections import deque

# Assuming TreeNode and ListNode definitions from Method 1

def convert_to_zigzag_iteratively(head):
    if not head:
        return None
    root = TreeNode(head.val)
    queue = deque([(root, head.next)])
    is_right = True
    while queue:
        level_size = len(queue)
        for _ in range(level_size):
            parent, current = queue.popleft()
            if current:
                if is_right:
                    parent.right = TreeNode(current.val)
                    queue.append((parent.right, current.next))
                else:
                    parent.left = TreeNode(current.val)
                    queue.append((parent.left, current.next))
        is_right = not is_right
    return root

# Example Usage
linked_list = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6))))))
binary_tree_root = convert_to_zigzag_iteratively(linked_list)

The output will be a binary tree root node which, when traversed, displays the zigzag level order structure.

This snippet defines an iterative function that builds each tree level using a queue data structure and swaps the child attachment direction after completing each level. The function ensures that each node in the linked list is placed correctly in the tree and that the level order zigzag pattern is observed.

Method 3: Using Two Stacks

A stack-based approach uses two stacks to maintain the current level and the next level, alternating their roles for each level of the tree. This method exploits the LIFO (Last-In-First-Out) property of stacks to reverse the order of nodes in alternate levels, achieving the zigzag pattern. It can be more intuitive for those familiar with depth-first tree traversals.

Here’s an example:

from collections import deque

# Assuming TreeNode and ListNode definitions from Method 1

def convert_to_zigzag_two_stacks(head):
    if not head:
        return None
    current_stack, next_stack = deque([TreeNode(head.val)]), deque()
    root = current_stack[0]
    head = head.next
    left_to_right = True
    while current_stack:
        node = current_stack.pop()
        if head:
            child = TreeNode(head.val)
            head = head.next
            if left_to_right:
                node.left = child
            else:
                node.right = child
            next_stack.append(child)
        if not current_stack:
            current_stack, next_stack = next_stack, deque()
            left_to_right = not left_to_right
    return root

# Example Usage
linked_list = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6))))))
binary_tree_root = convert_to_zigzag_two_stacks(linked_list)

The output will be a binary tree that zigzags as per the linked list ordering.

The code initializes two stacks for the current and next level of nodes. It processes nodes one-by-one from the current stack, creating children and adding them to the next stack. When the current stack is empty, the roles of the stacks are swapped and the direction of child attachment alternates, creating the zigzag pattern.

Method 4: Flatten and Construct

This method first flattens the linked list into an array to easily access nodes by their index. Then, it constructs the binary tree by computing the index of each child node based on the zigzag pattern, attaching children accordingly. This index-based approach simplifies the connection logic and can be easier to reason about when writing the code.

Here’s an example:

# Assuming TreeNode definition from Method 1

def list_to_array(head):
    array = []
    while head:
        array.append(TreeNode(head.val))
        head = head.next
    return array

def attach_children(nodes, level, total_levels):
    invert = level % 2 != 0
    for i in range(2**level - 1, min(2**(level + 1) - 1, len(nodes))):
        index = i if not invert else 2**(level + 1) - 1 - (i - 2**level + 1)
        if index * 2 + 1 < len(nodes):
            nodes[i].left = nodes[index * 2 + 1]
        if index * 2 + 2 < len(nodes):
            nodes[i].right = nodes[index * 2 + 2]

def convert_to_zigzag_flatten(head):
    node_array = list_to_array(head)
    total_levels = node_array.bit_length()
    for level in range(total_levels):
        attach_children(node_array, level, total_levels)
    return node_array[0] if node_array else None

# Example Usage
linked_list = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5, ListNode(6))))))
binary_tree_root = convert_to_zigzag_flatten(linked_list)

The output root node will yield a binary tree arranged according to the zigzag sequence derived from the linked list elements.

This solution transforms the linked list into an array, making it straightforward to reference nodes by index when attaching children. With the aid of a helper function that attaches children based on the current level and zigzag order, the binary tree is built iteratively level by level.

Bonus One-Liner Method 5: In-Place Modification

This theoretical method, though not practical due to Python’s lack of pointer manipulation used in lower-level languages like C++, suggests modifying the linked list nodes in-place to create a binary tree. This would involve overloading the next pointers to serve as tree left/right child pointers directly, using the list node structure to form the tree. Due to Python’s restrictions, this is ‘conceptual’ and serves as food for thought rather than a concrete implementation.

Here’s an example:

# Note: This is a theoretical one-liner and not executable Python code.
# It is only to demonstrate a concept.

binary_tree_root = theoretical_in_place_conversion(linked_list)

There is no actual output since this is a conceptual, non-executable example.

The idea behind this method is that if Python allowed for pointer manipulation (like C/C++), one could potentially reuse the list nodes structurally to form the binary tree without additional memory allocation. However, this is not feasible in Python due to its design.

Summary/Discussion

  • Method 1: Recursive Definition. It is naturally expressive and straightforward. However, recursion can lead to stack overflow with very long lists.
  • Method 2: Iterative Level-Building. Non-recursive, space-efficient iterative approach. May become complex when managing details of level transitions.
  • Method 3: Using Two Stacks. The stack method is intuitive for depth-first logic. Limited by the potential for large stack sizes equivalent to list length.
  • Method 4: Flatten and Construct. Array flattening allows for easy index-based child attachment. The downside is that full array reconstruction may be redundant and waste memory.
  • Bonus Method 5: In-Place Modification. This is a conceptual solution showcasing potential memory efficiency but is not applicable in Python.