# 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))))))
```

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

return None
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))))))
```

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

return None
root = current_stack[0]
left_to_right = True
while current_stack:
node = current_stack.pop()
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))))))
```

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

array = []
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]

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))))))
```

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.