csanim.com .Breadth-first search (BFS) of BST in Python - Visualization and Code
I mostly write about cs algorithms, data structures and code challenges.

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

Expand code
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

Expand code
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

Expand code
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

Expand code
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

Expand code
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:

Maximum Level Sum of a Binary Tree (Medium)

Binary Tree Level Order Traversal (Medium)

Author:

headshot-lg.jpg
Japhia
*no spam, just fresh content