Teaching Kids Programming – Breadth First Search Algorithm to Check the Completeness of a Binary Tree

Teaching Kids Programming: Videos on Data Structures and Algorithms

Given the root of a binary tree, determine if it is a complete binary tree.

In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Complte Binary Tree Validation Algorithm using BFS

With BFS (Breadth First Search) Algorithm, we traverse/visit the nodes level by level. And if we meet a hole and then afterwards we meet another node, we invalidate the completeness immediately.

At the begining, we initialize the hole (boolean type) to false, and the queue to contain the root node. While the queue has elements, we pop one (deque) and if the node is NULL, we set the hole flag to False, otherwise, if the hole is already true meaning we have seen a hole before, and we know it is not a complete binary tree.

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

# 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 isCompleteTree(self, root: TreeNode) -> bool:
        if root is None:
            return True
        q = deque([root])
        hole = False
        while q:
            p = q.popleft()
            if not p:
                hole = True
            else:
                if hole:
                    return False
                q.append(p.left)
                q.append(p.right)
        return True

# 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 isCompleteTree(self, root: TreeNode) -> bool:
        if root is None:
            return True
        q = deque([root])
        hole = False
        while q:
            p = q.popleft()
            if not p:
                hole = True
            else:
                if hole:
                    return False
                q.append(p.left)
                q.append(p.right)
        return True

The time complexity is O(N) where N is the number of the nodes in the given binary tree. As in the worst case (where it is a full binary tree), we have to visit each node exactly once. The space complexity is O(N) as we are using a queue to implement the BFS algorithm.

See also: Breadth First Search Algorithm to Check Completeness of a Binary Tree?

–EOF (The Ultimate Computing & Technology Blog) —