Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

958. Check Completeness of a Binary Tree

Time: $O(n)$

Space: $O(n)$

			


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();
  }
};




			


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();
  }
}




			


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 == nullptr)
      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 == nullptr)
      return true;
    if (index > count)
      return false;
    return validIndex(root->left, index * 2, count) &&
           validIndex(root->right, index * 2 + 1, count);
  }
};