958. Check Completeness of a Binary Tree LeetCode Solution
In this guide, you will get 958. Check Completeness of a Binary Tree LeetCode Solution with the best time and space complexity. The solution to Check Completeness of a Binary Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of 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
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
958. Check Completeness of a Binary Tree LeetCode Solution in C++
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();
}
}; /* code provided by PROGIEZ */
958. Check Completeness of a Binary Tree LeetCode Solution in Java
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();
}
} // code provided by PROGIEZ
958. Check Completeness of a Binary Tree LeetCode Solution in Python
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);
}
}; # code by PROGIEZ
