# Breadth-first search (BFS) of BST in Python - Visualization and Code

Learn how to implement Breadth-First Search of a Binary Search Tree in Python.

Breadth-first search (BFS or Level Order Traversal) is a method of traversing a tree or graph data structure. BFS uses the Queue data structure while depth-first algorithms use the Stack data structure.

The BFS algorithm starts at the root node and travels through every child node at the current level before moving to the next level.

BFS is an extremely common pattern used to solve algorithmic puzzles in technical interviews and competitive programming sites such as leetcode and hackerrank.

### Space and time complexity

Time complexity: `O(n)` where `n` is the number of nodes.

Space complexity: `O(b)` where `b` is maximum breadth.

Use case examples: BFS is often used for finding the shortest path or solving for a series of choices which can result in a winning or losing state.

Used in: Dijkstra's Algorithm, Ford-Fulkerson Algorithm

## Animated solution

#### Python's deque

We are using a regular array for our queue in the above sample for teaching purposes. In Python you may prefer `collections.deque` for fast O(1) appends and pops from either direction.

## bfs_traversal

``````def bfs(self, root=None):
if root is None:
return
queue = [root]

while len(queue) > 0:
cur_node = queue.pop(0)

if cur_node.left is not None:
queue.append(cur_node.left)

if cur_node.right is not None:
queue.append(cur_node.right)

# end

# initialize tree and start bfs traversal
root = Node(4)
root.insert_nodes([2, 1, 3, 6, 5, 7], root)
root.bfs(root=root)```
```

## Code breakdown - Iterative implementation

We'll start by initializing our tree - we'll create a tree identical to the animation above:

## bfs_traversal

``````def bfs(self, root=None):
if root is None:
return
queue = [root]

while len(queue) > 0:
cur_node = queue.pop(0)

if cur_node.left is not None:
queue.append(cur_node.left)

if cur_node.right is not None:
queue.append(cur_node.right)

# end

# initialize tree and start bfs traversal
root = Node(4)
root.insert_nodes([2, 1, 3, 6, 5, 7], root)
root.bfs(root=root)```
```

Let's make sure there is a valid root node and insert it as the first element of the queue:

## bfs_traversal

``````def bfs(self, root=None):
if root is None:
return
queue = [root]

while len(queue) > 0:
cur_node = queue.pop(0)

if cur_node.left is not None:
queue.append(cur_node.left)

if cur_node.right is not None:
queue.append(cur_node.right)

# end

# initialize tree and start bfs traversal
root = Node(4)
root.insert_nodes([2, 1, 3, 6, 5, 7], root)
root.bfs(root=root)```
```

## Queue with root node

40

Iterate through our queue. In each iteration we will dequeue the front node and keep reference to it as `cur_node` so we can check for child nodes:

## bfs_traversal

``````def bfs(self, root=None):
if root is None:
return
queue = [root]

while len(queue) > 0:
cur_node = queue.pop(0)

if cur_node.left is not None:
queue.append(cur_node.left)

if cur_node.right is not None:
queue.append(cur_node.right)

# end

# initialize tree and start bfs traversal
root = Node(4)
root.insert_nodes([2, 1, 3, 6, 5, 7], root)
root.bfs(root=root)```
```

## Updated Queue:

40

On each iteration we pop the oldest item from our queue while keeping reference to it in order to lookup it's child nodes.

If `cur_node` has a left child then append `left` to the back of the queue. Same for the `right` node:

## bfs_traversal

``````def bfs(self, root=None):
if root is None:
return
queue = [root]

while len(queue) > 0:
cur_node = queue.pop(0)

if cur_node.left is not None:
queue.append(cur_node.left)

if cur_node.right is not None:
queue.append(cur_node.right)

# end

# initialize tree and start bfs traversal
root = Node(4)
root.insert_nodes([2, 1, 3, 6, 5, 7], root)
root.bfs(root=root)```
```

## Updated queue

20
Front
61
Back

Queue after adding the left (`val: 2`) and right (`val: 6`) nodes.

And we are finished with our first iteration!

Let's look at the iteration code block in its entirety now and imagine you had a tree exactly like our top animation. Starting with a root value of 4 and a left of 2 and a right of 6, what would the queue look like after the first iteration?

## bfs_traversal

``````def bfs(self, root=None):
if root is None:
return
queue = [root]

while len(queue) > 0:
cur_node = queue.pop(0)

if cur_node.left is not None:
queue.append(cur_node.left)

if cur_node.right is not None:
queue.append(cur_node.right)

# end

# initialize tree and start bfs traversal
root = Node(4)
root.insert_nodes([2, 1, 3, 6, 5, 7], root)
root.bfs(root=root)```
```

## Queue after 1st iteration cycle:

2061

Next iteration cycle will dequeue Node with value `2` and enqueue it's child nodes.

If we look at the second iteration below, we follow the same sequence of steps but now we check the left & right of the `{val:2}` node. Since this node only has the `left` child node and no `right` node we only add a single new item to the queue:

## Queue after 2nd iteration:

206112

Continue iterating through until queue has no items remaining (reference the animation at the top to see the full cycle).

### Full sample code snippet

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

def __repr__(self):
return str(self.val)

def insert_node(self, val):
if self.val is not None:
if val < self.val:
if self.left is None:
self.left = Node(val)
else:
self.left.insert_node(val)
elif val > self.val:
if self.right is None:
self.right = Node(val)
else:
self.right.insert_node(val)

@staticmethod
def insert_nodes(vals: list, root):
for i in vals:
root.insert_node(i)

def bfs(self, root=None):
if root is None:
return
queue = [root]

while len(queue) > 0:
cur_node = queue.pop(0)

if cur_node.left is not None:
queue.append(cur_node.left)

if cur_node.right is not None:
queue.append(cur_node.right)

print(queue)

def run():
root = Node(4)
root.insert_nodes([2, 1, 3, 6, 5, 7], root)
root.bfs(root=root)```
```

Leetcode challenges using BFS: