Check Completeness of a Binary Tree in C++

Language Options

Code Solution


class Solution {
 public:
  bool isCompleteTree(TreeNode* root) {
    if (root == nullptr)
      return true;

    queue q{{root}};

    while (q.front() != nullptr) {
      TreeNode* node = q.front();
      q.pop();
      q.push(node->left);
      q.push(node->right);
    }

    while (!q.empty() && q.front() == nullptr)
      q.pop();

    return q.empty();
  }
};

Problem Description

So, you think you can just throw a bunch of nodes together and call it a binary tree? Well, think again! The problem at hand is to determine if a binary tree is “complete.” A complete binary tree is like that overachieving student in class who always has their homework done and is present for every lecture. In simpler terms, every level of the tree must be fully filled, except possibly for the last level, which should be filled from left to right.

Imagine a party where everyone is seated perfectly, except for that one guy who decided to stand in the corner. You know, the one who always shows up late and takes the last slice of pizza. That’s what an incomplete binary tree looks like!

Approach

The provided code uses a breadth-first search (BFS) approach to check the completeness of the binary tree. It utilizes a queue to traverse the tree level by level. The algorithm starts by enqueuing the root node. It continues to dequeue nodes and enqueue their children until it encounters a null node. If it finds any non-null nodes after a null node, it concludes that the tree is incomplete.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n), where n is the number of nodes in the tree. Each node is processed once.
Space Complexity	O(n) in the worst case, where the queue could store all the nodes at the last level of the tree.

Real-World Example

Think of a company where every department has to be fully staffed, except for the last department, which can have some empty desks. If you walk into the office and see that the marketing team is missing half its members while the finance team is fully staffed, you know something is off. Similarly, in a complete binary tree, if any level is missing nodes in the middle, it’s not complete!