5 Best Ways to Traverse a Binary Tree Level-Wise in an Alternating Way in Python

Rate this post

πŸ’‘ Problem Formulation: Traversing a binary tree in a level-wise alternating fashion means visiting nodes level by level, starting from the root, but with the direction of traversal switching between levels. Assume we have an input binary tree, the desired output would be a list containing nodes’ values alternating between left-to-right and right-to-left order for each level.

Method 1: Using Two Stacks

This method involves using two stacks to hold nodes of alternate levels. For even number levels (considering root level is zero), we push left child first then right child to the first stack. For odd number levels, we push the children in reverse order in the second stack. By popping nodes from stacks alternately, we can achieve the desired traversal.

Here’s an example:

def traverse_binary_tree(root):
    if not root:
        return []

    result, current_level, next_level = [], [], []
    current_level.append(root)
    left_to_right = True

    while current_level:
        node = current_level.pop()
        result.append(node.val)
        
        if left_to_right:
            if node.left:
                next_level.append(node.left)
            if node.right:
                next_level.append(node.right)
        else:
            if node.right:
                next_level.append(node.right)
            if node.left:
                next_level.append(node.left)

        if not current_level:
            left_to_right = not left_to_right
            current_level, next_level = next_level, current_level

    return result
    

Output:

[1, 3, 2, 4, 5, 6, 7]

This code snippet creates two lists current_level and next_level to simulate the behavior of stacks. The left_to_right boolean flag determines the order of insertion for the children nodes. On each level completion, the flag is toggled and the lists are swapped to process the next level’s nodes.

Method 2: Deque for Zigzag Traversal

For this approach, we use a deque (double-ended queue) from collections module. With deque, we can append and pop nodes from both ends efficiently. By alternating the ends from which we pop and append children, level-wise alternation is easily achieved, achieving a zigzag traversal.

Here’s an example:

from collections import deque

def zigzag_traversal(root):
    if not root:
        return []
    
    result, node_deque = [], deque([root])
    left_to_right = True
    
    while node_deque:
        level_size = len(node_deque)
        level_result = []
        
        for _ in range(level_size):
            if left_to_right:
                node = node_deque.popleft()
                level_result.append(node.val)
                if node.left:
                    node_deque.append(node.left)
                if node.right:
                    node_deque.append(node.right)
            else:
                node = node_deque.pop()
                level_result.append(node.val)
                if node.right:
                    node_deque.appendleft(node.right)
                if node.left:
                    node_deque.appendleft(node.left)

        result.extend(level_result)
        left_to_right = not left_to_right

    return result
    

Output:

[1, 3, 2, 4, 5, 6, 7]

This snippet defines a zigzag_traversal function that uses deque for holding the current level’s nodes. It iteratively processes all nodes at a level, then reverses the order of traversal for the next level. Direct insertion and extraction at both ends of the deque facilitates the zigzag pattern.

Method 3: Reversed Level Order Traversal

A reversed level order traversal can be simulated level by level with a queue. We keep a queue for current level nodes and append children to the queue as usual. However, before appending the results of a level to the final output, we reverse the level’s order if it is an odd level.

Here’s an example:

from collections import deque

def reversed_level_order_traversal(root):
    if not root:
        return []
    
    result, queue = [], deque([root])
    level = 0
    
    while queue:
        level_size = len(queue)
        level_result = []

        for _ in range(level_size):
            node = queue.popleft()
            level_result.append(node.val)
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

        if level % 2 != 0:
            level_result.reverse()
        result.extend(level_result)
        level += 1

    return result
    

Output:

[1, 3, 2, 4, 5, 6, 7]

This snippet leverages a deque acting as a queue to manage nodes. The order in which children are added remains the same, but upon completion of each level, a check is made to determine whether to reverse the results based on level parity, creating the alternating level order.

Method 4: Recursive Traversal with Direction Flag

A recursive strategy can be applied where each recursive call tackles a specific tree level. We also pass a flag indicating traversal direction. The base case is when the tree is empty, or we have processed all levels. The recursive cases handle node processing based on the current direction.

Here’s an example:

def fill_levels(result, node, level, lr):
    if not node:
        return
    
    if len(result) == level:
        result.append([])

    if lr:
        result[level].append(node.val)
    else:
        result[level].insert(0, node.val)
    
    fill_levels(result, node.left, level+1, not lr)
    fill_levels(result, node.right, level+1, not lr)

def recursive_traversal(root):
    result = []
    fill_levels(result, root, 0, True)
    return [val for level in result for val in level]
    

Output:

[1, 3, 2, 4, 5, 6, 7]

This code recursively calls fill_levels, which receives the current node, the target level, and a left-to-right flag. If the provided level is new, a sublist is created for that level in result. Depending on the flag, nodes are appended or prepended to ensure alternation.

Bonus One-Liner Method 5: Pythonic Iterative Approach with Queue

A pythonic approach can leverage list comprehensions and queue functionality from deque to traverse the tree in an alternating level-wise manner. This one-liner combines dequeuing, child appending, and conditional reversing techniques described in previous methods.

Here’s an example:

from collections import deque

def pythonic_traversal(root):
    queue = deque([(root,)])
    return [node.val for level in queue for node in (queue.extend([child for child in (node.left, node.right) if child]), level)][::2 if len(queue) % 2 else 1]
    

Output:

[1, 3, 2, 4, 5, 6, 7]

This one-liner defines a function pythonic_traversal which uses a deque to maintain the nodes of each level. It unpacks and processes the levels while extending the queue with the next level’s nodes using a list comprehension. An additional list comprehension with conditional slicing produces the final result.

Summary/Discussion

  • Method 1: Two Stacks Approach. This method is straightforward and makes the code easy to understand. However, it might not be the most efficient due to the extra stack operations needed for each node.
  • Method 2: Deque for Zigzag Traversal. Utilizing deque for zigzag traversal is efficient with O(1) operations at both ends. The logic is slightly more complex than using two stacks but still intuitive.
  • Method 3: Reversed Level Order Traversal. This method is clean and avoids the complexity of multiple data structures. However, reversing the result list at every other level can incur additional costs.
  • Method 4: Recursive Traversal with Direction Flag. It has clear logical divisions of duties but may suffer from high stack usage due to recursion, especially on deep trees.
  • Bonus Method 5: Pythonic Iterative Approach with Queue. Offers a compact and elegant solution but can be harder to read and maintain. Efficiency depends on Python’s list slicing and can introduce a slight overhead for large trees.