> For the complete documentation index, see [llms.txt](https://llssff.gitbook.io/coding-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://llssff.gitbook.io/coding-problems/tree-traversal/check-if-complete-tree.md).

# Check if complete tree

Medium

Check if a given binary tree is completed. A complete binary tree is one in which every level of the binary tree is completely filled except possibly the last level. Furthermore, all nodes are as far left as possible.

**Examples**

        5

      /    \\

    3        8

  /   \\

1      4

is completed.

        5

      /    \\

    3        8

  /   \        \\

1      4        11

is not completed.

**Corner Cases**

* What if the binary tree is null? Return true in this case.

**Recursive:** Check if index should not exist

```
/**
 * public class TreeNode {
 *   public int key;
 *   public TreeNode left;
 *   public TreeNode right;
 *   public TreeNode(int key) {
 *     this.key = key;
 *   }
 * }
 */
public class Solution {

  public int countNode(TreeNode root){
    if (root == null) return 0;
    return (1 + countNode(root.left) + countNode(root.right));
  }
  public boolean completeHelper(TreeNode root, int index, int nodeCount){
    if (root == null) return true;
    if (index >= nodeCount) return false;
    return completeHelper(root.left, 2 * index + 1, nodeCount) && 
      completeHelper(root.right, 2 * index + 2, nodeCount);

  }
  public boolean isCompleted(TreeNode root) {
    if (root == null) return true;
    int nodeCount = countNode(root);
    return completeHelper(root,  0, nodeCount);
    

  }
}

// time complexity: countNode O(N) + CompleteHelper O(N) = O(2N) = O(N)
// space complexity: no new instance created. O(1)

```

**BFS:** toggle boolean on first node doesn't have both children

```
public class Solution {
  public boolean isCompleted(TreeNode root) {
    if (root == null) return true;

    Queue<TreeNode> q = new LinkedList<>();
    q.add(root);
    boolean noMoreChildren = false;
    
    while (noMoreChildren == false) {
      // when we encounter a node with a null left or right child
      // no further nodes are allowed with children
      TreeNode current = q.poll();
      if (current.left == null) {
        noMoreChildren = true;
        // check for illegal right-only branch
        if (current.right != null) return false;
        break;
      }
      q.add(current.left);
      if (current.right == null) {
        noMoreChildren = true;
        break;
      }
      q.add(current.right);
    }

    while (!q.isEmpty()) {
      TreeNode current = q.poll();
      if (current.left != null || current.right != null) {
        return false;
      }
    }
    return true;
  }
}

//time complexity: O(N) one pass
//space complexity: O(N/2) queue size max = O(N)
```