5 Best Ways to Display the Nodes of a Tree Using BFS Traversal in Python

Rate this post

πŸ’‘ Problem Formulation: You need to traverse a tree data structure in Python and display its nodes in a level-by-level order. This technique, known as Breadth-First Search (BFS), requires an algorithm that visits all the nodes of a tree horizontally before moving to the next level. Our goal is to provide code examples that accomplish this task efficiently, with the input being a tree data structure and the output being a list of its nodes arranged according to BFS traversal.

Method 1: Using a Queue

Implementing BFS traversal using a queue is a classic approach. The method begins by placing the root node in the queue. While the queue is not empty, it continuously dequeues a node, outputs it, and enqueues its children. This process visits all nodes in a level-by-level fashion.

Here’s an example:

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key
  
def BFS(root):
    queue = []     # Initialize a queue
    queue.append(root)
    
    while len(queue) > 0:
        node = queue.pop(0)
        print(node.val, end = " ")
        
        # Enqueue left child
        if node.left is not None:
            queue.append(node.left)
            
        # Enqueue right child
        if node.right is not None:
            queue.append(node.right)

# Example Tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

BFS(root)

Output of this code:

1 2 3 4 5

This code snippet creates a simple tree with five nodes and traverses it using BFS traversal with the help of a queue. The function BFS() continually processes nodes from the queue and prints their values, ensuring that all nodes are visited in level-order.

Method 2: Using Recursion and Dictionary

This method uses recursion to visit each node and a dictionary to track nodes at each level. It is a bit more complex but also an interesting recursive twist to the standard BFS implementation.

Here’s an example:

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def BFS_recursive(nodes, level, dict_levels):
    if not nodes:
        return
      
    for node in nodes:
        if level not in dict_levels:
            dict_levels[level] = []
        dict_levels[level].append(node.val)
        
    children = []
    for node in nodes:
        if node.left:
            children.append(node.left)
        if node.right:
            children.append(node.right)
            
    BFS_recursive(children, level + 1, dict_levels)

def BFS_with_recursion(root):
    levels = {}
    BFS_recursive([root], 0, levels)
    for level_nodes in levels.values():
        for value in level_nodes:
            print(value, end=" ")

# Example Tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

BFS_with_recursion(root)

Output of this code:

1 2 3 4 5

The recursive approach splits the task of BFS into parts, obtaining all nodes at the current level, and recursively calling itself for the next level’s nodes. The dictionary levels acts as a container for nodes at various depths, which are printed in order after the traversal is complete.

Method 3: Using Iteration and List Comprehension

This method blends iterative logic and list comprehension to perform BFS traversal by operating directly on a list that represents the queue. It’s a more Pythonic and concise way to express the core idea behind BFS.

Here’s an example:

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def BFS_with_iteration(root):
    queue = [root]
    while queue:
        current = queue.pop(0)
        print(current.val, end=" ")
        queue += [child for child in (current.left, current.right) if child]

# Example Tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

BFS_with_iteration(root)

Output of this code:

1 2 3 4 5

In this approach, a list is used as a queue – nodes are popped from the beginning and children are appended to the end. The list comprehension within the loop concisely adds existing left and right children to continue the BFS traversal.

Method 4: Using a Deque

Utilizing a deque data structure from the collections module can optimize the BFS traversal. This method offers efficient append and pop operations from both ends of the deque, improving the performance over list operations.

Here’s an example:

from collections import deque

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def BFS_with_deque(root):
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val, end=" ")
        
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

# Example Tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

BFS_with_deque(root)

Output of this code:

1 2 3 4 5

By using a deque, the code avoids the costly list operations for popping from the beginning of the list. popleft() and append() operations on deque are more efficient and recommended for BFS implementations.

Bonus One-Liner Method 5: Functional Approach

A functional approach to BFS leverages the powerful itertools.chain and generator expressions to compactly perform the traversal in one line. It’s an elegant, albeit advanced, technique.

Here’s an example:

from itertools import chain

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def BFS_oneliner(root):
    level = [root]
    while level:
        print(' '.join(str(node.val) for node in level), end=" ")
        level = list(chain.from_iterable((node.left, node.right) for node in level if node))

# Example Tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

BFS_oneliner(root)

Output of this code:

1 2 3 4 5

This snippet elegantly handles BFS by maintaining a list of nodes at the current level and using chain.from_iterable() to flatten and filter out None values for the next level, all in a single line loop body.

Summary/Discussion

  • Method 1: Using a Queue. Robust and straightforward. However, dequeuing from a list is not efficient for large trees.
  • Method 2: Using Recursion and Dictionary. Creative and organized. It can be more memory intensive due to recursion and dictionary overhead.
  • Method 3: Using Iteration and List Comprehension. Clean and Pythonic. Shares the same queue inefficiency as method 1 with large data sets.
  • Method 4: Using a Deque. Optimal for performance. Slightly less readable for newcomers to algorithms compared to the basic queue.
  • Bonus One-Liner Method 5: Functional Approach. Compact and advanced. May sacrifice readability for brevity and is not ideal for those unfamiliar with functional programming concepts.