Teaching Kids Programming – BFS Algorithm to Compute the Maximum Depth of the Binary Tree

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Yesterday, we use the DFS (Depth First Search) Algorithm to compute the Max Distance (Max Depth) from root to leaf node: Teaching Kids Programming – Recursive Algorithm to Compute the Maximum Depth of the Binary Tree

Today, we are going to use the BFS (Breadth First Search) algorithm to achieve the same task.

Compute the Max Depth using Breadth First Search Algorithm

We use the BFS (Breadth First Search) Algorithm to perform a level-by-level traversal. We need to remember the node and its current level. Thus we push the node and depth as a tuple into a queue. In Python, we use deque (double ended queue) which allows us to do append and pop in both ends.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        q = deque([(root, 1)])
        ans = 0
        while len(q) > 0:
            cur, depth = q.popleft()
            ans = max(ans, depth)
            if cur.left:
                q.append((cur.left, depth + 1))
            if cur.right:
                q.append((cur.right, depth + 1))
        return ans

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        q = deque([(root, 1)])
        ans = 0
        while len(q) > 0:
            cur, depth = q.popleft()
            ans = max(ans, depth)
            if cur.left:
                q.append((cur.left, depth + 1))
            if cur.right:
                q.append((cur.right, depth + 1))
        return ans

The time complexity is O(N) and the space complexity is also O(N) where N is the number of the nodes in the given binary tree. For each node dequed from the queue, we push its left and right node (if not empty) to the rear of the queue i.e. enqueue operation.

Compute the Maximum Depth for a N-ary Tree:

• Teaching Kids Programming – Maximum Depth of N-ary Tree via Depth First Search or Breadth First Search Algorithms
• Teaching Kids Programming – BFS Algorithm to Compute the Maximum Depth of the Binary Tree
• Teaching Kids Programming – Recursive Algorithm to Compute the Maximum Depth of the Binary Tree
• C++ Coding Exercise – Find Maximum Depth of N-ary Tree

–EOF (The Ultimate Computing & Technology Blog) —