Check Completeness of a Binary Tree - Practice Coding Problems

Check Completeness of a Binary Tree - Problem

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 2^h nodes inclusive at the last level h.

Input & Output

Example 1 — Complete Binary Tree

$ Input: root = [1,2,3,4,5,6]

› Output: true

💡 Note: All levels are filled completely, and the last level nodes (4,5,6) are as far left as possible. This satisfies the definition of a complete binary tree.

Example 2 — Incomplete Binary Tree

$ Input: root = [1,2,3,4,5,null,7]

› Output: false

💡 Note: Node 7 exists but node 6 is missing. In a complete binary tree, all nodes in the last level must be as far left as possible, so there should be no gaps.

Example 3 — Single Node

$ Input: root = [1]

› Output: true

💡 Note: A single node tree is always complete - it has only one level with one node, which satisfies all completeness conditions.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Binary tree in level-order representation

Check

Verify nodes are filled left-to-right with no gaps

Output

Return true if complete, false otherwise

Key Takeaway

🎯 Key Insight: In a complete binary tree, BFS will encounter all non-null nodes before any null nodes

Asked in

F Facebook 15 A Amazon 12 M Microsoft 8

The key insight is that in a complete binary tree, once we encounter a null node during level-order traversal, all subsequent nodes must also be null. The optimal BFS approach gives us Time: O(n), Space: O(w) where w is the maximum width of the tree.

Common Approaches

Approach	Time	Space	Notes
✓ Level-by-Level Counting	O(n)	O(h)	Count nodes at each level and verify completeness rules
BFS with Null Detection	O(n)	O(w)	Use BFS and stop when first null is encountered - all remaining must be null

Level-by-Level Counting — Algorithm Steps

Step 1: Find tree depth using DFS
Step 2: Count nodes at each level
Step 3: Verify each level has correct node count
Step 4: Check last level is left-aligned

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Depth

Find tree height using DFS

Count Each Level

Verify each level has expected node count

Check Last Level

Ensure last level is left-aligned

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <math.h>

struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

struct TreeNode* createNode(int val) {
    struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int getDepth(struct TreeNode* node) {
    if (!node) return 0;
    int leftDepth = getDepth(node->left);
    int rightDepth = getDepth(node->right);
    return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
}

int countNodesAtLevel(struct TreeNode* node, int targetLevel, int currentLevel) {
    if (!node) return 0;
    if (currentLevel == targetLevel) return 1;
    return countNodesAtLevel(node->left, targetLevel, currentLevel + 1) + 
           countNodesAtLevel(node->right, targetLevel, currentLevel + 1);
}

bool isLastLevelComplete(struct TreeNode* node, int level, int targetLevel) {
    if (!node) return true;
    if (level == targetLevel) return true;
    
    bool leftComplete = true;
    bool rightComplete = true;
    
    if (node->left) {
        leftComplete = isLastLevelComplete(node->left, level + 1, targetLevel);
    }
    if (node->right) {
        if (!node->left) return false;
        rightComplete = isLastLevelComplete(node->right, level + 1, targetLevel);
    }
    
    return leftComplete && rightComplete;
}

bool solution(struct TreeNode* root) {
    if (!root) return true;
    
    int depth = getDepth(root);
    
    // Check all levels except last are full
    for (int level = 0; level < depth - 1; level++) {
        int expected = (int)pow(2, level);
        int actual = countNodesAtLevel(root, level, 0);
        if (actual != expected) return false;
    }
    
    return isLastLevelComplete(root, 0, depth - 1);
}

int main() {
    // For simplicity, assume a basic test case
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    
    bool result = solution(root);
    printf(result ? "true\n" : "false\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Multiple tree traversals to count nodes at each level

✓ Linear Growth

Space Complexity

O(h)

Recursion stack for DFS traversal where h is tree height

✓ Linear Space

89.2K Views

Medium Frequency

~15 min Avg. Time

1.9K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Level-by-Level Counting — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler