How do you solve Check Completeness of a Binary Tree on LeetCode?

Check Completeness of a Binary Tree (LeetCode #958) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: A complete binary tree must fill each level completely, except possibly the last.

What is the brute force solution for Check Completeness of a Binary Tree?

The brute force approach for Check Completeness of a Binary Tree is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each level of the binary tree one by one to see if it's completely filled. If we find any gaps in the last level or if any previous level is not filled, we can conclude that the tree is not complete. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Check Completeness of a Binary Tree?

Check Completeness of a Binary Tree uses the following concepts: Tree, Breadth-First Search, Binary Tree. The recommended patterns to study are: Breadth-First Search, Level Order Traversal.

What are the interview tips for Check Completeness of a Binary Tree?

Explain your thought process clearly while coding. Consider edge cases, such as trees with only one node. Discuss the time and space complexities of your solution.

What are common mistakes when solving Check Completeness of a Binary Tree?

Not handling null nodes correctly during traversal. Confusing complete binary trees with full binary trees.

#958

Check Completeness of a Binary Tree

Medium

TreeBreadth-First SearchBinary TreeBreadth-First SearchLevel Order Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a level-order traversal while keeping track of the number of nodes and their indices. This helps us determine if the tree is complete by checking if the indices of the nodes follow the complete binary tree properties.

⚙️

Algorithm

3 steps

1Step 1: Perform a level-order traversal and keep track of the index of each node based on its position in a complete binary tree.
2Step 2: Compare the index of each node with the expected index to ensure they match the complete binary tree structure.
3Step 3: If any index is found that does not match the expected index, return false.

solution.py22 lines

1# Full working Python code
2from collections import deque
3
4class TreeNode:
5    def __init__(self, val=0, left=None, right=None):
6        self.val = val
7        self.left = left
8        self.right = right
9
10
11def isCompleteBinaryTree(root):
12    if not root:
13        return True
14    queue = deque([(root, 0)])
15    index = 0
16    while queue:
17        node, idx = queue.popleft()
18        if node:
19            queue.append((node.left, 2 * idx + 1))
20            queue.append((node.right, 2 * idx + 2))
21            index += 1
22    return index == len(queue)

ℹ

Complexity note: The time complexity is O(n) because we visit each node once. The space complexity is O(n) due to the queue used for level-order traversal, which can grow to the size of the last level of the tree.

1A complete binary tree must fill each level completely, except possibly the last.
2In the last level, nodes must be as far left as possible.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.