#958

Medium

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Check Completeness of a Binary Tree

Determine if a binary tree is complete by verifying its node structure and leftmost placement in the last level.

Problem Statement

Given the root of a binary tree, determine if it is a complete binary tree. A binary tree is considered complete if every level, except possibly the last, is completely filled. Additionally, all nodes in the last level must be as far left as possible.

The challenge is to check whether the tree satisfies this definition of completeness, where missing nodes must appear on the right and not disrupt the leftmost structure. If a node appears further right than expected, the tree is incomplete.

Examples

Example 1

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

Output: true

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

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

Solution Approach

Breadth-First Search (BFS) Traversal

The most effective way to determine if a tree is complete is by using a BFS traversal. We traverse level by level, and once we encounter a null value, we expect all subsequent nodes to also be null. Any non-null node after encountering null signifies that the tree is incomplete.

Tracking Node Position

While performing BFS, it's important to track whether the current node is at the expected position in the tree. If the tree is complete, the nodes should appear in a level-order sequence, with no gaps in the sequence for any non-null nodes.

Space Optimization

Optimizing the space complexity can be achieved by reducing the storage of nodes during traversal. For instance, by using a queue to hold nodes level-by-level and minimizing extra state tracking, we can efficiently check the completeness without using unnecessary memory.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity of the solution depends on the number of nodes in the tree, O(N), since every node must be visited at least once during the traversal. The space complexity also depends on the tree's structure, but in the worst case, it can be O(N) due to the storage required for the BFS queue.

What Interviewers Usually Probe

Focus on the ability to traverse trees efficiently.
Ensure the candidate considers how to handle null nodes and left-to-right order.
Evaluate the candidate's awareness of space optimization techniques during traversal.

Common Pitfalls or Variants

Common pitfalls

Failing to account for the placement of nodes after encountering null values.
Misunderstanding the completeness condition for the last level.
Not considering the space complexity and unnecessarily storing large amounts of data during traversal.

Follow-up variants

Modified versions where the tree can be non-binary.
Cases where the tree structure is less balanced, requiring different traversal strategies.
Variation with constraints on tree height, making certain optimization techniques more important.

FAQ

What defines a complete binary tree?

A complete binary tree is one where all levels are fully filled except possibly the last, which must be filled from left to right.

How can BFS be used to check for tree completeness?

BFS allows us to traverse the tree level-by-level and ensure that after a null node is encountered, all subsequent nodes must also be null to satisfy completeness.

What are common mistakes when solving this problem?

A common mistake is failing to correctly track null nodes and left-to-right order, which can lead to incorrectly marking a tree as complete or incomplete.

What other algorithms could be used for this problem?

Other tree traversal algorithms, like DFS, could be adapted to solve the problem, but BFS is typically more intuitive for checking completeness in a level-order manner.

How does GhostInterview assist in this problem?

GhostInterview helps by guiding the user through BFS traversal, offering suggestions on handling edge cases, and optimizing time and space complexity.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:
        q = deque([root])
        while q:
            node = q.popleft()
            if node is None:
                break
            q.append(node.left)
            q.append(node.right)
        return all(node is None for node in q)

Continue Practicing

#965 univalued binary tree #987 vertical order traversal of a binary tree #993 cousins in binary tree