Check Completeness of a Binary Tree

A complete binary tree is the shape behind heaps and array-based trees. So checking if a tree has that shape comes up a lot. The trick the interviewer wants to see is small. Once you find an empty spot, no real node is allowed to appear after it. Spot that rule and the problem is solved.

🎯 The Problem

You get a binary tree and must say whether it is complete.

The rules:

• A binary tree is a structure where each node has a value and up to two children.
• Complete means every level is fully filled, except maybe the last one.
• The last level fills from the left with no gaps in the middle.
• Return true if the tree follows this shape, otherwise false.

Input (complete):          Input (not complete):
        1                          1
       / \                        / \
      2   3                      2   3
     / \  /                     /     \
    4  5 6                      4       7

Output: true                   Output: false

Explanation:
  Left tree fills every level, last level packed from the left.
  Right tree has a gap: 2 is missing a right child, but 3 still has a right child.

Here is the complete tree. Notice the last level packs tight from the left with no holes.

🔢 Approach 1: Number the Nodes by Index (Brute Force)

The idea in one line: store the tree as an array and check that the indices have no holes.

The idea:

• Give the root index 0.
• A node at index i has its left child at 2*i + 1 and right child at 2*i + 2.
• This is the same math heaps use.

How it works:

• Walk the tree and hand out indices this way.
• In a complete tree with n nodes, every index stays between 0 and n - 1.
• Find the largest index used. If it equals n - 1, the tree is complete.

Why it is weak:

• The indices can grow very large on a one-sided tree.
• Those big numbers can overflow on big inputs.
• It is correct but fragile, so we want something safer.

Here is the index-numbering code:

def is_complete_tree(root):
    nodes = []
    def dfs(node, index):
        if node:
            nodes.append(index)
            dfs(node.left, 2 * index); dfs(node.right, 2 * index + 1)
    dfs(root, 1)
    return len(nodes) == max(nodes) if nodes else True

⚡ Approach 2: BFS With a Null Flag (Best)

The idea in one line: read the tree row by row, and the moment you pass an empty spot, no real node may come after it.

The idea:

• Use BFS, short for breadth-first search, which reads each full row before the next using a queue.
• Do not skip missing children. Push null into the queue when a child is absent.
• A null just marks an empty spot.

How it works:

• Keep one flag seen_null, starting false.
• Pop items off the queue one by one.
• When you pop a null, set the flag to true.
• After the flag is true, if you pop a real node, the tree is not complete.

Why it is fast:

• A real node after an empty spot is exactly the gap a complete tree forbids.
• One pass over the nodes and one flag answer the whole question.
• No huge index numbers, so no overflow.

This diagram shows the flag flipping when the first empty spot appears, and how any later real node fails the check.

Steps to Solve

1. If the tree is empty, it counts as complete.
2. Put the root in a queue. Set a flag seen_null to false.
3. While the queue is not empty, pop the front item.
4. If the item is null, set seen_null to true and continue.
5. If the item is a real node but seen_null is already true, return false.
6. Otherwise push the node’s left child, then its right child, even when they are null.
7. If the loop finishes without failing, return true.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int val;
    struct Node *left, *right;
} Node;

Node* newNode(int v) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->val = v; n->left = n->right = NULL;
    return n;
}

int isComplete(Node* root) {
    if (!root) return 1;
    Node* queue[1000];
    int head = 0, tail = 0;
    queue[tail++] = root;
    int seenNull = 0;
    while (head < tail) {
        Node* cur = queue[head++];
        if (cur == NULL) {
            seenNull = 1;              // first empty spot found
        } else {
            if (seenNull) return 0;    // real node after a gap
            queue[tail++] = cur->left;  // push children, even NULL
            queue[tail++] = cur->right;
        }
    }
    return 1;
}

int main(void) {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);

    printf("%s\n", isComplete(root) ? "true" : "false");
    return 0;
}

true

#include <iostream>
#include <queue>
using namespace std;

struct Node {
    int val;
    Node *left, *right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

bool isComplete(Node* root) {
    if (!root) return true;
    queue<Node*> q;
    q.push(root);
    bool seenNull = false;
    while (!q.empty()) {
        Node* cur = q.front(); q.pop();
        if (cur == nullptr) {
            seenNull = true;            // first empty spot
        } else {
            if (seenNull) return false; // real node after a gap
            q.push(cur->left);          // push children, even null
            q.push(cur->right);
        }
    }
    return true;
}

int main() {
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);

    cout << (isComplete(root) ? "true" : "false") << endl;
    return 0;
}

true

import java.util.*;

public class IsComplete {
    static class Node {
        int val;
        Node left, right;
        Node(int v) { val = v; }
    }

    static boolean isComplete(Node root) {
        if (root == null) return true;
        Queue<Node> q = new LinkedList<>();
        q.add(root);
        boolean seenNull = false;
        while (!q.isEmpty()) {
            Node cur = q.poll();
            if (cur == null) {
                seenNull = true;            // first empty spot
            } else {
                if (seenNull) return false; // real node after a gap
                q.add(cur.left);            // push children, even null
                q.add(cur.right);
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Node root = new Node(1);
        root.left = new Node(2);
        root.right = new Node(3);
        root.left.left = new Node(4);
        root.left.right = new Node(5);
        root.right.left = new Node(6);

        System.out.println(isComplete(root));
    }
}

true

from collections import deque


class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def is_complete(root):
    if not root:
        return True
    queue = deque([root])
    seen_null = False               # have we passed an empty spot yet?
    while queue:
        cur = queue.popleft()
        if cur is None:
            seen_null = True        # mark the first gap
        else:
            if seen_null:
                return False        # a real node after a gap means not complete
            queue.append(cur.left)  # push children, even if None
            queue.append(cur.right)
    return True


root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
print(is_complete(root))

True

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

function isComplete(root) {
  if (!root) return true;
  const queue = [root];
  let seenNull = false;            // passed an empty spot yet?
  while (queue.length) {
    const cur = queue.shift();
    if (cur === null) {
      seenNull = true;             // mark the first gap
    } else {
      if (seenNull) return false;  // real node after a gap
      queue.push(cur.left);        // push children, even null
      queue.push(cur.right);
    }
  }
  return true;
}

const root = new Node(1);
root.left = new Node(2);
root.right = new Node(3);
root.left.left = new Node(4);
root.left.right = new Node(5);
root.right.left = new Node(6);
console.log(isComplete(root));

true

Let us read the Python version line by line, since the flag rule is the whole answer.

The line if not root: return True treats an empty tree as complete. There is nothing to break the rule, so it passes.

The line queue = deque([root]) starts the BFS with the root. A deque lets us pop from the front quickly.

The line seen_null = False sets the flag. It asks one question: have we already passed an empty spot? At the start, no.

The line cur = queue.popleft() takes the next item from the front. Items come out in level order, top row before bottom row, left before right.

The branch if cur is None: seen_null = True handles an empty spot. We do not stop here. We just remember that a gap happened.

The branch if seen_null: return False is the real check. If a real node shows up while the flag is already true, a node came after a gap. A complete tree never allows that. So we fail right away.

The two queue.append lines push both children, even when they are None. Pushing the empty spots on purpose is what lets the flag catch a gap. If we skipped None children, we could never see the gap.

The final return True runs only when the whole queue drained without a real node ever following a gap. That means the tree is complete.

⏱️ Time and Space Complexity

The index way walks every node once, so it is O(n), but its indices can grow huge and overflow on awkward trees. The BFS flag way also visits each node once and pushes at most a few extra null markers. So it is a clean O(n) with no overflow worry. Both keep a queue, so both use O(n) memory in the worst case.

🧩 Key Takeaways

• ✅ A complete tree fills every level, and the last level packs from the left with no gaps.
• ✅ Read the tree in level order with BFS, pushing empty spots as null too.
• ✅ Keep a flag that turns true the first time you pop a null.
• ✅ After the flag is true, any real node means the tree is not complete.
• ✅ The whole check is one pass and runs in O(n) without index overflow.

🚀 What’s Next?

• Find Leaves of Binary Tree
• Convert BST to Sorted Doubly Linked List