# Check Completeness of a Binary Tree
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/check-completeness-of-a-binary-tree)
Canonical: https://scaleengineer.com/dsa/problems/check-completeness-of-a-binary-tree
**Algorithms:** [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Lyft](https://scaleengineer.com/companies/lyft)
---
## Problem
Given the `root` of a binary tree, determine if it is a _complete binary tree_.

In a **[complete binary tree](http://en.wikipedia.org/wiki/Binary%5Ftree#Types%5Fof%5Fbinary%5Ftrees)**, 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 `2h` nodes inclusive at the last level `h`.

**Example 1:**

![](https://assets.glich.co/dsa/check-completeness-of-a-binary-tree/image0.png) 

**Input:** root = [1,2,3,4,5,6]
**Output:** true
**Explanation:** Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

**Example 2:**

![](https://assets.glich.co/dsa/check-completeness-of-a-binary-tree/image1.png) 

**Input:** root = [1,2,3,4,5,null,7]
**Output:** false
**Explanation:** The node with value 7 isn't as far left as possible.

**Constraints:**

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

# Approaches
## DFS with Node Indexing (Flawed)
This approach uses a Depth-First Search (DFS) traversal. We can attempt to determine if a tree is complete by treating it as if it were stored in an array, where each node has a specific index. For a node at index `i`, its left child is at `2*i` and its right child is at `2*i+1`. A tree would be complete if the total number of nodes equals the maximum index found. However, this approach has a critical flaw for deep trees.
**Time:** O(N), where N is the number of nodes. We visit each node exactly once. · **Space:** O(H), where H is the height of the tree, due to the recursion stack. For a complete tree, H is O(log N). For a skewed tree, H is O(N).
**Pros:** For trees that are 'bushy' or close to complete, it is more space-efficient (O(log N)) than BFS (O(N)).
**Cons:** The logic is less intuitive than the BFS approach.; Critically, the node indices can grow exponentially with the depth of the tree (`2^depth`). For a skewed tree with N nodes, the depth can be N. With N=100, the index `2^99` would overflow even a 64-bit integer (`long`), making this approach fail for deep, sparse trees that are permitted by the problem constraints.; Relies on recursion, which can lead to stack overflow for extremely deep trees (also an issue with N=100).
### Explanation
The idea is to assign an "ID" or "index" to each node. The root is assigned index 1. For any node at index `i`, its left child gets index `2*i` and its right child gets `2*i+1`.

We perform a DFS traversal of the tree, counting the total number of nodes and finding the maximum index assigned to any node. After the traversal, we compare the count and the max index. If they are equal, the tree is complete. 

This logic works for 'bushy' trees, but fails for deep, skewed trees due to integer overflow, as the index can grow exponentially with depth.

```java
// NOTE: This solution is flawed and will fail for deep, skewed trees due to integer overflow.
class Solution {
    private int count = 0;
    private long maxIndex = 0; // Using long to delay overflow, but it still happens for N > 62

    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }
        dfs(root, 1L);
        return count == maxIndex;
    }

    private void dfs(TreeNode node, long index) {
        if (node == null) {
            return;
        }
        count++;
        maxIndex = Math.max(maxIndex, index);
        // Stop recursion to prevent overflow, but this is just a patch.
        // A correct solution shouldn't rely on indices that can grow this large.
        if (index >= Long.MAX_VALUE / 2) return;
        dfs(node.left, 2 * index);
        dfs(node.right, 2 * index + 1);
    }
}
```
### Algorithm
- Create a helper DFS function, say `dfs(node, index)`.
- In the main function, initialize `node_count = 0` and `max_index = 0`.
- Call `dfs(root, 1)`.
- After the call returns, compare `node_count` and `max_index`. Return `true` if they are equal, `false` otherwise.
- The `dfs(node, index)` function:
  - If `node` is `null`, return.
  - Increment `node_count`.
  - Update `max_index = max(max_index, index)`.
  - Recursively call `dfs(node.left, 2 * index)`.
  - Recursively call `dfs(node.right, 2 * index + 1)`.

## Level-Order Traversal (BFS)
This approach uses Breadth-First Search (BFS) to traverse the tree level by level. It is a robust and intuitive method for this problem. The core idea is that in a complete binary tree, once a null node is encountered in the level-order traversal, all subsequent nodes must also be null.
**Time:** O(N), where N is the number of nodes in the tree. Each node is enqueued and dequeued exactly once. · **Space:** O(W), where W is the maximum width of the binary tree. In the worst case (a complete binary tree), the last level can contain up to `ceil(N/2)` nodes, so the space complexity is O(N).
**Pros:** Intuitive and directly follows the definition of a complete binary tree.; Robust and works correctly for all trees within the given constraints.; Relatively easy to implement.
**Cons:** Can be less space-efficient than a DFS approach for 'bushy' trees where the width `W` is proportional to `N`.
### Explanation
We perform a level-order traversal starting from the root using a queue.

We iterate through the tree level by level. When we encounter the first `null` node, it signifies the potential end of the tree's nodes.

We use a boolean flag, `endFound`, initialized to `false`. When we dequeue a `null` node, we set this flag to `true`.

If we ever dequeue a non-`null` node after `endFound` has been set to `true`, it means there's a gap in the tree, violating the "as far left as possible" rule. In this case, the tree is not complete, and we return `false`.

If a node is not `null`, we enqueue its left and right children, even if they are `null`. This is crucial to detect gaps.

If the traversal completes without violating the condition, the tree is complete, and we return `true`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isCompleteTree(TreeNode root) {
        if (root == null) {
            return true;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean endFound = false;

        while (!queue.isEmpty()) {
            TreeNode currentNode = queue.poll();

            if (currentNode == null) {
                endFound = true;
            } else {
                if (endFound) {
                    return false; // Found a non-null node after a null node
                }
                queue.offer(currentNode.left);
                queue.offer(currentNode.right);
            }
        }
        return true;
    }
}
```
### Algorithm
- If the `root` is `null`, return `true` (an empty tree is complete).
- Initialize a queue (`java.util.Queue`) and add the `root` to it.
- Initialize a boolean flag `endFound = false`.
- Loop while the queue is not empty:
  - Dequeue the current node.
  - If the current node is `null`, set `endFound = true`.
  - If the current node is not `null`:
    - If `endFound` is `true`, it means we found a node after a null gap. Return `false`.
    - Enqueue the left child (`node.left`).
    - Enqueue the right child (`node.right`).
- If the loop finishes, return `true`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { public boolean isCompleteTree ( TreeNode root ) { Deque < TreeNode > q = new LinkedList <>(); q . offer ( root ); while ( q . peek () != null ) { TreeNode node = q . poll (); q . offer ( node . left ); q . offer ( node . right ); } while (! q . isEmpty () && q . peek () == null ) { q . poll (); } return q . isEmpty (); } }
```

### CPP

```cpp
/** * 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: bool isCompleteTree ( TreeNode * root ) { queue < TreeNode *> q { { root } }; while ( q . front ()) { root = q . front (); q . pop (); q . push ( root -> left ); q . push ( root -> right ); } while ( ! q . empty () && ! q . front ()) q . pop (); return q . empty (); } };
```

### Python

```python
# 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 : TreeNode ) -> bool : q = deque ([ root ]) while q : node = q . popleft () if node is None : break q . append ( node . left ) q . append ( node . right ) return all ( node is None for node in q )
```