Practice/Meta/Leetcode 958. Check Completeness of a Binary Tree

Leetcode 958. Check Completeness of a Binary Tree

CodingMust

Problem

Given the root of a binary tree, determine if it is a complete binary tree.

A binary tree is considered complete when:

• Every level, except possibly the deepest level, contains the maximum number of nodes
• All nodes in the deepest level are positioned as far to the left as possible

In other words, if you were to fill the tree level by level from left to right, there should be no "gaps" where a null position appears before any remaining non-null nodes.

Requirements

1. Return true if the tree satisfies the complete binary tree property
2. Return false if any gaps exist in the level-order traversal before the final node
3. Handle edge cases including empty trees and single-node trees
4. The solution should work for trees with up to 100 nodes

Constraints

• The number of nodes in the tree is in the range [1, 100]
• 1 <= Node.val <= 1000
• Expected time complexity: O(n) where n is the number of nodes
• Expected space complexity: O(n) for the traversal queue

Examples

Example 1:

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

Output: true Explanation: Every level except the last is completely filled, and all nodes in the last level are as far left as possible. `

Example 2:

` Input: root = [1,2,3,4,5,null,7] 1 /
2 3 / \
4 5 7

Output: false Explanation: Node 3 is missing its left child but has a right child. This creates a gap in the level-order structure. `

Example 3:

` Input: root = [1] 1

Output: true Explanation: A tree with a single node is complete by definition. `