# 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.

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.

## 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

*0*

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:

*0*

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

*0*

*1*

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:

*0*6

*1*

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:

*0*6

*1*1

*2*

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

### Full sample code snippet

Leetcode challenges using BFS:

Maximum Level Sum of a Binary Tree (Medium)

Binary Tree Level Order Traversal (Medium)