## Algorithm

Problem Name: 958. Check Completeness of a Binary Tree

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

Example 1:

```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:

```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`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
int d;
bool shrinked;
} dep_t;
bool verify_depth(dep_t *dep, int d) {
if (dep->d == -1) {    // first time verifying a depth
dep->d = d;
return true;
}

// assert(d  < = dep->d);
if (d == dep->d - 1 && !dep->shrinked) {
dep->d --;
dep->shrinked = true;
}

if (d == dep->d) {
return true;
}
return false;
}
bool traversal(struct TreeNode *node, dep_t *dep, int d) {
if (!node) {
if (!verify_depth(dep, d)) return false;
} else {
if (!traversal(node->left, dep, d + 1)) return false;
if (!traversal(node->right, dep, d + 1)) return false;
}

return true;
}
bool isCompleteTree(struct TreeNode* root) {
dep_t dep = { -1, false };
return traversal(root, &dep, 0);
}
``````
Copy The Code &

Input

cmd
root = [1,2,3,4,5,6]

Output

cmd
true

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public boolean isCompleteTree(TreeNode root) {
boolean end = false;
while (!queue.isEmpty()) {
TreeNode removed = queue.poll();
if (removed == null) {
end = true;
} else {
if (end) {
return false;
}
}
}
return true;
}
}
``````
Copy The Code &

Input

cmd
root = [1,2,3,4,5,6]

Output

cmd
true

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const isCompleteTree = function(root) {
let cur = [root]
let depth = 1
while(cur.length) {
const nxt = []
// console.log(cur)
for(let i = 0; i  <  cur.length; i++) {
const e = cur[i]
if(e == null) nxt.push(null, null)
else if(e) nxt.push(e.left, e.right)
}

if(!valid(cur) || (cur[cur.length - 1] == null && valid(nxt))) {
return false
}

if(nxt.some(e => e != null)) {
cur = nxt
} else {
cur = []
}
depth++
}

return true

function valid(arr) {
let firstNull = arr.length, lastNonNull = arr.length
for(let i = 0; i < arr.length; i++) {
const e = arr[i]
if(firstNull === arr.length && e == null) firstNull = i
if(e != null) lastNonNull = i
}
// console.log(firstNull, lastNonNull>
return firstNull >= lastNonNull
}
};
``````
Copy The Code &

Input

cmd
root = [1,2,3,4,5,null,7]

Output

cmd
false

### #4 Code Example with C# Programming

```Code - C# Programming```

``````
class Solution:
def isCompleteTree(self, root):
q, pre = [root, None], 1
while any(q):
i = q.index(None)
if any(q[i:]) or pre > 1:
return False
pre = len(q[i:])
q = [child for node in q[:i] for child in (node.left, node.right)] + [None]
return True
``````
Copy The Code &

Input

cmd
root = [1,2,3,4,5,null,7]

Output

cmd
false