Check Completeness of a Binary Tree

Medium · Graphs · Explanation and code example

Depth First Search (Optimal)

How it works

We can verify completeness in a single DFS pass by tracking the tree's height and whether we have seen a "short" path (one that ends before the maximum depth). In a complete tree, all paths to null nodes at the deepest level must appear before any paths ending one level higher, when traversing left to right.

Steps

  1. Track the tree height (initialized to 0) and a flag nullSeen (for detecting gaps).
  2. Perform DFS, tracking the current height:
    • When reaching a null node, set treeHgt if not set.
    • If the null is at height (treeHgt - 1), mark nullSeen = true.
    • If the null is at treeHgt after nullSeen is true, return false (gap detected).
  3. Recursively check left then right children.
  4. Return true if no gaps are detected.

Complexity

  • Time complexity: O(n)
  • Space complexity: O(n) for recursion stack.

Things to watch for

Not Adding Null Children to Queue

When using BFS, both left and right children must be added to the queue even if they are null. Skipping null children prevents detection of gaps in the tree, since the null marker is needed to identify when a non-null node appears after a gap.

Checking Only Immediate Children for Completeness

A tree can have a missing left child but present right child, which violates completeness. Simply checking if both children exist misses cases where a null appears in the middle of a level.

Wrong Index Formula in DFS Approach

When using array-based indexing (root at 0, children at 2i+1 and 2i+2), using incorrect formulas causes false positives. A common mistake is using 2i and 2i+1, which corresponds to 1-indexed arrays instead of 0-indexed.

Python code example

from typing import Optional

# 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: Optional[TreeNode]) -> bool:
        treeHgt = 0
        nullSeen = False

        def dfs(node, hgt):
            nonlocal treeHgt, nullSeen
            if not node:
                if treeHgt == 0:
                    treeHgt = hgt
                elif hgt == treeHgt - 1:
                    nullSeen = True
                elif hgt != treeHgt:
                    return False
                return not (hgt == treeHgt and nullSeen)

            return dfs(node.left, hgt + 1) and dfs(node.right, hgt + 1)

        return dfs(root, 0)

C++ code example

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int treeHgt = 0;
    bool nullSeen = false;

    bool dfs(TreeNode* node, int hgt) {
        if (!node) {
            if (treeHgt == 0) {
                treeHgt = hgt;
            } else if (hgt == treeHgt - 1) {
                nullSeen = true;
            } else if (hgt != treeHgt) {
                return false;
            }
            return !(hgt == treeHgt && nullSeen);
        }

        return dfs(node->left, hgt + 1) && dfs(node->right, hgt + 1);
    }

    bool isCompleteTree(TreeNode* root) {
        return dfs(root, 0);
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode Watch NeetCode on YouTube

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations