How to perform breadth-first search on a binary search tree in Python?

Question

Jayant Kumar · Accepted Answer

Table of Contents
Introduction
Breadth-First Search (BFS) is a graph traversal algorithm that explores nodes level by level. When applied to a Binary Search Tree (BST), BFS traverses nodes level by level starting from the root. This traversal method is particularly useful for operations that require processing nodes in their hierarchical order.
1. Breadth-First Search (BFS) Overview
BFS Traversal Method
BFS uses a queue to keep track of nodes to be explored:

Start from the root node.
Enqueue the root node and mark it as visited.
Dequeue a node, process it, and enqueue its children (left and right).
Repeat the process until the queue is empty.

Use Cases

Level-order Traversal: Print nodes level by level.
Shortest Path in Unweighted Graphs: Not typically used for BST, but BFS is efficient in general graphs for this purpose.
Breadth-first Exploration: Useful for algorithms that need to explore all nodes at the current level before moving deeper.

2. Python Implementation of BFS on a Binary Search Tree
Binary Search Tree Implementation
First, let's define a simple BST and the BFS traversal method.
from collections import deque

class BSTNode:
    def __init__(self, key):
        self.value = key
        self.left = None
        self.right = None

class BinarySearchTree:
    def __init__(self):
        self.root = None

# Insert a node into the BST
    def insert(self, key):
        if self.root is None:
            self.root = BSTNode(key)
        else:
            self._insert_recursive(self.root, key)

def _insert_recursive(self, current, key):
        if key &#x3C; current.value:
            if current.left is None:
                current.left = BSTNode(key)
            else:
                self._insert_recursive(current.left, key)
        else:
            if current.right is None:
                current.right = BSTNode(key)
            else:
                self._insert_recursive(current.right, key)

# Breadth-First Search (BFS) traversal
    def bfs(self):
        if self.root is None:
            return
        
        queue = deque([self.root])
        
        while queue:
            node = queue.popleft()
            print(node.value, end=' ')
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)

Example Usage
Here's how to use the BinarySearchTree class and perform a BFS traversal.
# Create a Binary Search Tree and insert some nodes
bst = BinarySearchTree()
bst.insert(50)
bst.insert(30)
bst.insert(20)
bst.insert(40)
bst.insert(70)
bst.insert(60)
bst.insert(80)

print("BFS Traversal:")
bst.bfs()  # Output: 50 30 70 20 40 60 80

Conclusion
Performing Breadth-First Search (BFS) on a Binary Search Tree (BST) involves using a queue to traverse nodes level by level. This traversal method is useful for operations requiring hierarchical processing of nodes. By implementing BFS in Python, you can efficiently explore and manage BST structures, facilitating various applications such as level-order traversal and hierarchical data processing.

How to perform breadth-first search on a binary search tree in Python?

Similar Questions