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 == nullptr)
      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
class Solution {
 public:
  bool isCompleteTree(TreeNode* root) {
    const int count = getCount(root);
    return validIndex(root, 1, count);
  }

 private:
  int getCount(TreeNode* root) {
    if (root == nullptr)
      return 0;
    return 1 + getCount(root->left) + getCount(root->right);
  }

  // Returns true if there's no index > the number of nodes.
  bool validIndex(TreeNode* root, int index, int count) {
    if (root == nullptr)
      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 count = getCount(root);
    return validIndex(root, 1, count);
  }

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

  // Returns true if there's no index > the number of nodes.
  private boolean validIndex(TreeNode root, int index, int count) {
    if (root == null)
      return true;
    if (index > count)
      return false;
    return validIndex(root.left, index * 2, count) && validIndex(root.right, index * 2 + 1, count);
  }
}