Check Completeness of a Binary Tree

Medium
1934.

Check Completeness of a Binary Tree

Check Completeness of a Binary Tree is a medium coding problem on breadth-first search and trees, asked in Amazon, Microsoft and Meta interviews.

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

In a complete binary tree every level is completely filled except possibly the last one, and all nodes of the last level are as far left as possible. (The last level h may hold anywhere from 1 to 2^h nodes.)

Example 1

Input
root = [1,2,3,4,5,6]
Output
true
Explanation
The first two levels are full and the last one, 4 5 6, is packed to the left.

Example 2

Input
root = [1,2,3,4,5,null,7]
Output
false
Explanation
On the last level there is a gap (3 has no left child) before 7.

Example 3

Input
root = [1,2,3,null,4]
Output
false
Explanation
2 has a right child but no left child, so the last level is not packed to the left.

Constraints

  • The number of nodes in the tree is in the range [1, 100]
  • 1 <= Node.val <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isCompleteTree = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Check Completeness of a Binary Tree — Problem & Solution

Check Completeness of a Binary Tree solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Check Completeness of a Binary Tree is a medium coding problem on breadth-first search and trees, asked in Amazon, Microsoft and Meta interviews.

Problem statement

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

In a complete binary tree every level is completely filled except possibly the last one, and all nodes of the last level are as far left as possible. (The last level h may hold anywhere from 1 to 2^h nodes.)

Example 1

Input: root = [1,2,3,4,5,6]
Output: true
Explanation: The first two levels are full and the last one, 4 5 6, is packed to the left.

Example 2

Input: root = [1,2,3,4,5,null,7]
Output: false
Explanation: On the last level there is a gap (3 has no left child) before 7.

Example 3

Input: root = [1,2,3,null,4]
Output: false
Explanation: 2 has a right child but no left child, so the last level is not packed to the left.

Constraints

  • The number of nodes in the tree is in the range [1, 100]
  • 1 <= Node.val <= 1000

Hints for Check Completeness of a Binary Tree

  1. Hint 1

    Read the tree in level order, writing down a marker for every missing child as well as every node.

  2. Hint 2

    In a complete tree, all the real nodes come first and all the missing ones after — once you meet a gap, nothing real may follow.

  3. Hint 3

    So run a BFS that also enqueues null children; after the first null is dequeued, any non-null node means the tree is not complete.

How to solve Check Completeness of a Binary Tree

A complete tree, read level by level from left to right, is a contiguous run of nodes followed only by empty slots. A BFS that enqueues null children sees exactly that sequence, so the tree is complete if no node appears after the first null.

Approach

  1. Put the root in a queue and set seenGap = false.
  2. Dequeue an entry. If it is null, set seenGap = true and continue.
  3. If it is a node and seenGap is already true, return false. Otherwise enqueue both of its children, null or not.
  4. If the queue empties without a violation, return true.

Why it works

The BFS produces the nodes in the order of their positions in a complete-tree numbering, with a null at every missing position whose parent exists. The tree is complete exactly when the occupied positions are 1..n with no hole, i.e. when no real node follows a null in that order.

Complexity

  • Time — O(n)
  • Space — O(n) for the queue

Pitfalls

  • Enqueue null children too — skipping them hides the gaps the check is looking for.
  • A node with a right child but no left child is never complete.
  • Checking only that every level but the last is full is not enough; the last level must also be packed to the left.

Reference solution

Python

from typing import Optional

def isCompleteTree(root: Optional[TreeNode]) -> bool:
    queue = [root]
    head = 0
    seen_gap = False
    while head < len(queue):
        node = queue[head]
        head += 1
        if node is None:
            seen_gap = True
            continue
        if seen_gap:
            return False
        queue.append(node.left)
        queue.append(node.right)
    return True

Java

public static boolean isCompleteTree(TreeNode root) {
    List<TreeNode> queue = new ArrayList<>();
    queue.add(root);
    boolean seenGap = false;
    for (int h = 0; h < queue.size(); h++) {
        TreeNode node = queue.get(h);
        if (node == null) { seenGap = true; continue; }
        if (seenGap) return false;
        queue.add(node.left);
        queue.add(node.right);
    }
    return true;
}

C++

bool isCompleteTree(TreeNode* root) {
    vector<TreeNode*> queue = {root};
    bool seenGap = false;
    for (size_t h = 0; h < queue.size(); h++) {
        TreeNode* node = queue[h];
        if (!node) { seenGap = true; continue; }
        if (seenGap) return false;
        queue.push_back(node->left);
        queue.push_back(node->right);
    }
    return true;
}

JavaScript

var isCompleteTree = function(root) {
    var queue = [root], seenGap = false;
    for (var h = 0; h < queue.length; h++) {
        var node = queue[h];
        if (node === null) { seenGap = true; continue; }
        if (seenGap) return false;
        queue.push(node.left);
        queue.push(node.right);
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 156 breadth-first search problems · the whole catalogue

Learn the technique: Breadth-First Search (BFS) · Binary Trees and Tree Traversals