⚡Flashcard Drill➔
NeetCode #437LC-958MediumTrees
← Back to All Problems

#437 · #958 · Check Completeness of a Binary Tree(二叉树的完全性检验)

📌 Problem Statement & Constraints

Given the root of a binary tree, determine whether it is a complete binary tree: every level except possibly the last is full, and all nodes on the last level are as far left as possible. Constraints: the number of nodes is in [1, 100].

💡 Core Algorithmic Approaches

  1. A complete tree, read in level order, has no node after the first None.
  2. So do a BFS that also enqueues None children, and stop accepting nodes once a None has been seen.
  3. If any real node appears after a None, the tree is not complete.
  4. This is the simplest and most robust check.

💻 Benchmark Python3 Implementation

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        from collections import deque
        q = deque([root])
        seen_null = False
        while q:
            node = q.popleft()
            if not node:
                seen_null = True           # the first gap
                continue
            if seen_null:
                return False               # a node after a gap -> incomplete
            # enqueue children including None, so gaps are visible
            q.append(node.left)
            q.append(node.right)
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each node (and null slot) is dequeued once.
💾 Space Complexity
O(w) for the widest level.

⚠️ Interview Pitfalls & Follow-ups

  • Skipping None children when enqueuing: the gaps would be invisible and every tree would look complete.
  • Returning True when the queue empties with seen_null set: that is the correct outcome -- the check is for nodes *after* the gap.
  • Counting nodes and comparing with the expected complete-tree size: it works but requires the height and is more code.
  • Assuming the tree is balanced: completeness is a different property.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Trees Problems