Implementing Breadth-First Search to Traverse a Binary Tree in Python

Updated: at 04:23 AM

Breadth-first search (BFS) is an algorithm used to traverse or search through a tree or graph data structure. It explores all the nodes at the present depth prior to moving on to the nodes at the next depth level. In contrast to depth-first search which goes deep down a single branch before exploring other branches, BFS traverses the tree level-by-level from top to bottom and from left to right.

BFS has various applications in graphs and trees such as finding the shortest path between two nodes, solving maze puzzles, web crawling, peer-to-peer networks, and more. When applied to a binary tree, BFS can be used to traverse the tree in a level-order manner and calculate the minimum distance between the root node and any other node.

In this comprehensive guide, we will cover the following topics related to implementing a BFS algorithm to traverse a binary tree in Python:

Table of Contents

Open Table of Contents

Overview of Breadth-First Search on Binary Trees

Breadth-first search (BFS) is a tree/graph traversal algorithm that explores nodes level-by-level starting from the root node and moving down to the leaf nodes. The key characteristic of BFS is that it visits all the nodes at a given level before proceeding to the nodes at the next level.

Some key properties of BFS algorithm are:

In terms of binary trees, BFS explores the tree horizontally level by level. The traversal order follows:

  1. Visit the root node first.
  2. Move to the left subtree and traverse all nodes.
  3. Finally, move to the right subtree and traverse all nodes.

The nodes on each level are visited from left to right. Below is a sample BFS traversal order on a binary tree:

            A
          /   \
         B     C
       /  \     \
      D    E     F

BFS Order: A B C D E F

Some applications of breadth-first search for binary trees include:

Now let’s look at the algorithm logic and pseudocode for BFS on binary trees.

BFS Algorithm Logic and Pseudocode

The breadth-first search algorithm relies on a queue data structure to traverse a tree in a level-order manner. Here are the logical steps involved:

  1. Start by inserting the root node into a queue.

  2. Create a loop that will run as long as there are nodes still left in the queue.

  3. For each iteration:

    a. Dequeue the front node from the queue.

    b. Process the node, e.g. print its value.

    c. Check if the dequeued node has a left child, if yes enqueue the left child node.

    d. Check if the dequeued node has a right child, if yes enqueue the right child node.

  4. Repeat steps 2 and 3 until the queue is empty.

The above logical steps can be converted into the following BFS pseudocode for binary trees:

BFS(rootNode):

  //create empty queue
  queue = []

  //mark rootNode as visited and enqueue
  queue.enqueue(rootNode)

  while queue is not empty:

    //dequeue front node from queue
    currentNode = queue.dequeue()

    //process current node
    Process(currentNode)

    //check if left child exists, enqueue if so
    if currentNode.leftChild exists:
       queue.enqueue(currentNode.leftChild)

    //check if right child exists, enqueue if so
    if currentNode.rightChild exists:
       queue.enqueue(currentNode.rightChild)

  end while

end BFS

This covers the key logic behind implementing BFS traversal on binary trees. Next, we’ll analyze the time and space complexity.

Time and Space Complexity Analysis

The time complexity of the BFS algorithm on a binary tree is O(N), where N is the total number of nodes in the binary tree. This is because BFS traverses through each node eventually.

In the worst case scenario, when the tree is a complete binary tree, the traversal will have to traverse all levels of the tree, therefore the worst case time complexity is O(N).

The space complexity for BFS on a binary tree is O(W), where W is the maximum width or number of nodes at any level. This space is occupied by the queue to store nodes of a single level.

In the worst case, the space complexity can be O(N) when the binary tree is skewed and has a maximum width of N/2 nodes.

Now that we have covered the basics of BFS, let’s explore the data structure concepts relevant to binary trees in Python.

Binary Tree Data Structure in Python

Before we can implement BFS on binary trees in Python, we need to understand how binary trees are represented in Python through different data structures.

A binary tree is defined as a tree data structure where each node has at most two children termed left child and right child. Some key properties of binary trees are:

There are different types of binary trees:

Full Binary Tree - Every node has 0 or 2 children. All leaf nodes are at 2 levels.

Complete Binary Tree - All levels except the last have maximum nodes. The last level has all nodes to the left side.

Perfect Binary Tree - All internal nodes have 2 children and all leaf nodes are at the same level. Perfect trees are complete by definition.

In Python, a binary tree can be represented in various ways:

Using a Node Class

We can create a Node class which stores a value and pointers to the left and right child nodes:

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

Linked Structure

Each node stores reference to child nodes forming a linked structure:

          A
       /    \
      B      C
    /  \     / \
   D    E   F   G

List of Lists

A list of lists can represent a binary tree level by level:

binary_tree = [[1], [2,3], [4,5,6]]

Dictionary

We can also store child nodes in a dictionary format:

binary_tree = {
  'value': 1,
  'left': {
    'value': 2,
    'left': {
      'value': 4
    },
    'right': {
      'value': 5
    }
  },
  'right': {
    'value': 3,
    'left': {
      'value': 6
    }
  }
}

These are some common ways to represent binary trees in Python before implementing BFS.

Implementing BFS Algorithm to Traverse Binary Tree

Now we are ready to implement the bread-first search algorithm to traverse a binary tree in Python.

The key steps for BFS implementation are:

Initialize Data Structures

We need a visited set to track visited nodes and prevent repeating nodes. This can be a Python set or dictionary.

We also need a queue (FIFO) to store nodes of each level while traversing. This can be a normal queue or deque object.

visited = set() # Set to track visited nodes
queue = deque() # Initialize queue

Start by Enqueuing Root Node

We start BFS by visiting the root node and enqueue it to the queue.

root_node = get_root() # Get root reference
queue.append(root_node)
visited.add(root_node)

Loop While Queue is Not Empty

We process each node in the queue sequentially by:

while queue:

  current = queue.popleft() #dequeue front

  # process current node
  print(current.value)

  if current.left and current.left not in visited:
    queue.append(current.left)
    visited.add(current.left)

  if current.right and current.right not in visited:
   queue.append(current.right)
   visited.add(current.right)

We continue this iterative dequeuing, enqueueing and processing until the queue is empty.

BFS vs DFS Comparison

Breadth-first search (BFS) has some differences compared to depth-first search (DFS) when traversing binary trees:

Traversal Order

Use Cases

Time Complexity

Space Complexity

Queue vs Stack

To summarize, BFS vs DFS have tradeoffs to consider based on the problem we are solving. BFS gives horizontal level-order traversal while DFS gives vertical top-down traversal.

Example Python Code for BFS Binary Tree Traversal

Here is example Python code implementing BFS traversal on a sample binary tree:

from collections import deque

# Binary tree node class
class Node:
  def __init__(self, val=0, left=None, right=None):
    self.val = val
    self.left = left
    self.right = right

# BFS function to traverse binary tree
def traverseBFS(root):

  if not root:
    return

  queue = deque()
  queue.append(root)

  while queue:

    current = queue.popleft()
    print(current.val, end=' ')

    if current.left:
      queue.append(current.left)

    if current.right:
      queue.append(current.right)

# Construct sample binary tree
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# Traverse tree BFS
print("Breadth-First Traversal:")
traverseBFS(root)

Output:

Breadth-First Traversal:
1 2 3 4 5

This performs a level-order traversal by visiting nodes from left to right on each depth level. The queue helps maintain nodes level-wise in proper BFS order.

Applications of BFS on Binary Trees

Breadth-first search traversal of binary trees has several real-world applications:

Finding Minimum Depth of Binary Tree

We can find the minimum depth by traversing level-by-level and returning the level count once a leaf node is found.

Printing Level Order Traversal

BFS allows printing nodes level-by-level in proper horizontal order.

Finding Level Averages and Sums

We can calculate sum or average of node values at each level while traversing the tree.

Level of Node

We can find the level of a target node by incrementing level counter in BFS until the target is reached.

Shortest Path Between Nodes

BFS can find the shortest path between two nodes by tracking parent pointers.

Serialize and Deserialize Binary Tree

We can construct a binary tree back from its level order traversal string generated using BFS.

Peer-to-Peer Networking

BFS helps model peer-to-peer network connections and data transfers level-wise.

These are some common applications of breadth-first search when working with binary trees.

Summary and Key Takeaways

To summarize, here are the key points to remember when implementing breadth-first search traversal on binary trees in Python:

Breadth-first search provides an efficient way to traverse binary trees level-wise. Mastering BFS implementation in Python is key for tree-based algorithms and interview questions.

Some recommendations for further exploration are studying applications of BFS on graph data structures, comparing additional tree traversal algorithms, and practicing BFS coding problems to improve mastery.