Skip to content

958. Check Completeness of a Binary Tree 👍

Approach 1: BFS

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
 public:
  bool isCompleteTree(TreeNode* root) {
    if (!root)
      return true;

    queue<TreeNode*> q{{root}};

    while (q.front() != nullptr) {
      TreeNode* node = q.front();
      q.pop();
      q.push(node->left);
      q.push(node->right);
    }

    while (!q.empty() && q.front() == nullptr)
      q.pop();

    return q.empty();
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public boolean isCompleteTree(TreeNode root) {
    if (root == null)
      return true;

    Queue<TreeNode> q = new LinkedList<>(Arrays.asList(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();
  }
}

Approach 2: DFS

  • Time: $O(n)$
  • Space: $O(h)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
 public:
  bool isCompleteTree(TreeNode* root) {
    const int count = getCount(root);
    return validIndex(root, 1, count);
  }

 private:
  // calculate the # of nodes
  int getCount(TreeNode* root) {
    if (!root)
      return 0;
    return 1 + getCount(root->left) + getCount(root->right);
  }

  // make sure no index is > the # of nodes
  bool validIndex(TreeNode* root, int index, int count) {
    if (!root)
      return true;
    if (index > count)
      return false;

    return validIndex(root->left, index * 2, count) &&
           validIndex(root->right, index * 2 + 1, count);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
  public boolean isCompleteTree(TreeNode root) {
    final int nNodes = count(root);
    return isValidIndex(root, 1, nNodes);
  }

  private int count(TreeNode root) {
    if (root == null)
      return 0;
    return 1 + count(root.left) + count(root.right);
  }

  private boolean isValidIndex(TreeNode root, int i, int nNodes) {
    if (root == null)
      return true;
    if (i > nNodes)
      return false;
    return isValidIndex(root.left, i * 2, nNodes) &&
           isValidIndex(root.right, i * 2 + 1, nNodes);
  }
}
Back to top