Leetcode 958: Check Completeness of a Binary Tree

Input: The input consists of the root of a binary tree represented by the 'TreeNode' structure, where each node has a value, a left child, and a right child.

Example: Input: root = [1, 2, 3, 4, 5, 6]

Constraints:

• The number of nodes in the tree is between 1 and 100.

• 1 <= Node.val <= 1000.

Output: Return true if the binary tree is a complete binary tree, otherwise return false.

Example: Output: true

Constraints:

• The function should return a boolean indicating whether the tree is complete.

Goal: The goal is to verify that every level, except possibly the last, is completely filled and that all nodes in the last level are as far left as possible.

Steps:

• 1. Traverse the binary tree using level-order traversal.

• 2. At each step, check if the current node is null. If it is null, ensure that no nodes exist after it in the same level.

• 3. If all levels are filled correctly and the last level's nodes are as far left as possible, return true. Otherwise, return false.

Goal: The input tree must adhere to the constraints of having between 1 and 100 nodes, with node values between 1 and 1000.

Steps:

• The tree will contain between 1 and 100 nodes.

• Node values will be between 1 and 1000.

Assumptions:

• The binary tree is provided as a 'TreeNode' object.

• Input: Input: root = [1, 2, 3, 4, 5, 6]

• Explanation: In this case, every level before the last is filled completely, and all nodes in the last level are as far left as possible. Therefore, the tree is a complete binary tree.

• Input: Input: root = [1, 2, 3, 4, 5, null, 7]

• Explanation: In this case, the node with value 7 is not as far left as possible in the last level. Therefore, the tree is not a complete binary tree.

Approach: The approach to solving this problem involves performing a level-order traversal and ensuring that all levels are filled correctly, except possibly the last one, which must have all nodes as far left as possible.

Observations:

• Level-order traversal is ideal for this type of problem because it processes nodes level by level.

• We need to track the nodes at each level, ensuring that the last level’s nodes are positioned as far left as possible and no nodes exist after a null node in the level.

Steps:

• 1. Implement a level-order traversal using a queue.

• 2. Traverse the tree and at each level, if a null node is encountered, ensure all subsequent nodes are also null.

• 3. If we encounter any nodes after a null, return false. Otherwise, if the traversal completes without issues, return true.

Empty Inputs:

• The tree will always contain at least one node, as per the constraints.

Large Inputs:

• For larger trees (up to 100 nodes), the solution should still perform efficiently as long as the traversal is done correctly.

Special Values:

• The tree can contain null nodes, but we must ensure that they appear only after all other nodes at the same level.

Constraints:

• The tree will always have between 1 and 100 nodes, and node values are bounded between 1 and 1000.

bool isCompleteTree(TreeNode* root) {
    vector<TreeNode*> q;
    q.push_back(root);
    int i = 0;
    while(i < q.size() && q[i]) {
        q.push_back(q[i]->left);
        q.push_back(q[i]->right);
        i++;
    }
    while(i < q.size() && !q[i])
        i++;
    return i == q.size();
}

1 : Function Declaration

bool isCompleteTree(TreeNode* root) {

Function declaration for `isCompleteTree`, which determines if a binary tree is complete.

2 : Data Structure Initialization

    vector<TreeNode*> q;

Initialize a vector `q` to simulate a queue for level-order traversal.

3 : Push Root Node

    q.push_back(root);

Add the root node to the queue as the starting point for traversal.

4 : Variable Initialization

    int i = 0;

Initialize a variable `i` to track the current index in the queue.

5 : Traversal Loop

    while(i < q.size() && q[i]) {

Iterate over the queue, processing non-null nodes during level-order traversal.

6 : Add Left Child

        q.push_back(q[i]->left);

Add the left child of the current node to the queue, even if it's null.

7 : Add Right Child

        q.push_back(q[i]->right);

Add the right child of the current node to the queue, even if it's null.

8 : Increment Index

        i++;

Move to the next node in the queue.

9 : Null Node Check

    while(i < q.size() && !q[i])

Continue iterating through the queue, ensuring all subsequent nodes are null.

10 : Increment Index for Null Nodes

        i++;

Move to the next node while verifying the null condition.

11 : Return Condition

    return i == q.size();

Return true if all nodes are processed and null nodes appear only at the end of the queue.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: Where n is the number of nodes in the binary tree. In all cases, we visit each node once.

Best Case: O(1)

Worst Case: O(n)

Description: The space complexity is O(n) in the worst case due to the space used by the queue during the level-order traversal.

Leetcode 958: Check Completeness of a Binary Tree

Explore →