LeetCode 958 - Check Completeness of a Binary Tree

The problem asks us to determine whether a given binary tree is a complete binary tree. A complete binary tree has a specific structural property: every level, except possibly the last, is completely filled, and in the last level, all nodes appear as far left as possible.

leetcodemediumtreebreadth-first-searchbinary-tree

LeetCode Problem 958

Difficulty: 🟡 Medium
Topics: Tree, Breadth-First Search, Binary Tree

Solution

Problem Understanding

The problem asks us to determine whether a given binary tree is a complete binary tree. A complete binary tree has a specific structural property: every level, except possibly the last, is completely filled, and in the last level, all nodes appear as far left as possible. The input is the root of a binary tree, which is a pointer or reference to the top node of the tree. The expected output is a boolean value true if the tree is complete and false otherwise.

The constraints tell us that the tree will have between 1 and 100 nodes, and all node values are positive integers up to 1000. This is a small enough scale that an algorithm with linear time complexity, O(n), will be efficient.

Important edge cases include trees that are:

  1. Only a single node, which is trivially complete.
  2. Fully filled, which is also complete.
  3. Missing nodes on the last level but aligned left, which is complete.
  4. Missing nodes in the middle of the last level, which is not complete.

The problem guarantees that the tree is non-empty, so we do not need to handle None as input.

Approaches

A brute-force approach could involve traversing the tree and collecting nodes level by level, then checking after traversal whether the nodes align to form a complete structure. One could, for example, perform a level-order traversal, record None positions for missing children, and ensure no node appears after a None. This works but requires extra bookkeeping and is slightly less elegant.

The key observation for an optimal approach is that during a breadth-first traversal, once a None child is encountered, all subsequent nodes in level order must also be None for the tree to be complete. This observation allows a simple linear scan using a queue to check completeness without extra complexity.

Approach Time Complexity Space Complexity Notes
Brute Force O(n) O(n) Level-order traversal while recording structure, then check alignment
Optimal O(n) O(n) BFS with early stopping after first None, simplest and elegant

Algorithm Walkthrough

  1. Initialize a queue with the root node. This queue will be used for level-order traversal (BFS).
  2. Perform BFS by repeatedly dequeuing a node.
  3. If the node is not None, enqueue its left and right children into the queue.
  4. If the node is None, set a flag indicating that all following nodes must also be None.
  5. Continue processing the queue. If a non-None node is found after the flag has been set, return false because this violates completeness.
  6. If the queue is processed without violating the rule, return true.

Why it works: The invariant is that in a complete binary tree, once a missing child is observed at any level, no further children should exist in level-order traversal. BFS ensures we process nodes level by level, so encountering a None followed by a non-None node directly violates the completeness property.

Python Solution

# 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

from collections import deque
from typing import Optional

class Solution:
    def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
        if not root:
            return True
        
        queue = deque([root])
        end = False
        
        while queue:
            node = queue.popleft()
            if node:
                if end:
                    return False
                queue.append(node.left)
                queue.append(node.right)
            else:
                end = True
        
        return True

The implementation initializes a queue for BFS and iterates over all nodes. When None is encountered, the end flag is set to enforce that all subsequent nodes must also be None. This directly maps to the algorithm steps.

Go Solution

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isCompleteTree(root *TreeNode) bool {
    if root == nil {
        return true
    }

    queue := []*TreeNode{root}
    end := false

    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]

        if node != nil {
            if end {
                return false
            }
            queue = append(queue, node.Left)
            queue = append(queue, node.Right)
        } else {
            end = true
        }
    }
    return true
}

The Go solution mirrors the Python approach. Go requires explicit handling of nil pointers, and slices are used for the queue, with append operations for enqueuing children.

Worked Examples

Example 1: [1,2,3,4,5,6]

Step Queue State Node Processed end Result
1 [1] 1 False enqueue 2,3
2 [2,3] 2 False enqueue 4,5
3 [3,4,5] 3 False enqueue 6,None
4 [4,5,6,None] 4 False enqueue None,None
5 [5,6,None,None,None] 5 False enqueue None,None
6 [6,None,None,None,None,None] 6 False enqueue None,None
7 [None,...] None True continue
Queue fully processed - - True return True

Example 2: [1,2,3,4,5,null,7]

Step Queue State Node Processed end Result
1 [1] 1 False enqueue 2,3
2 [2,3] 2 False enqueue 4,5
3 [3,4,5] 3 False enqueue None,7
4 [4,5,None,7] 4 False enqueue None,None
5 [5,None,7,None,None] 5 False enqueue None,None
6 [None,7,None,None,None,None] None True continue
7 [7,None,None,None,None] 7 True return False

Complexity Analysis

Measure Complexity Explanation
Time O(n) Every node is visited exactly once in BFS
Space O(n) The queue can hold up to n/2 nodes at the last level

Since the tree has at most 100 nodes, this complexity is well within acceptable limits.

Test Cases

# Basic test cases
assert Solution().isCompleteTree(TreeNode(1)) == True  # single node
assert Solution().isCompleteTree(TreeNode(1, TreeNode(2), TreeNode(3))) == True  # perfect tree
assert Solution().isCompleteTree(TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(6), None))) == False  # missing left node in last level

# Provided examples
root1 = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, TreeNode(6)))
assert Solution().isCompleteTree(root1) == True

root2 = TreeNode(1, TreeNode(2, TreeNode(4), TreeNode(5)), TreeNode(3, None, TreeNode(7)))
assert Solution().isCompleteTree(root2) == False

# Edge cases
root3 = TreeNode(1, TreeNode(2, TreeNode(4), None), TreeNode(3))
assert Solution().isCompleteTree(root3) == False  # missing middle node
Test Why
single node Minimum tree size, trivially complete
perfect tree Fully filled tree, always complete
missing left node in last level Non-left alignment, should return False
provided example 1 Matches problem illustration, True expected
provided example 2 Matches problem illustration, False expected
missing middle node Non-left alignment at last level, edge case

Edge Cases

  1. Single-node tree: This is the simplest complete binary tree. The algorithm handles it by initializing the queue with the root. Since there are no children, the BFS completes successfully and returns true.
  2. Last level partially filled left-aligned: If the last level has some nodes missing but all nodes are aligned to the left, the BFS will encounter None after all valid nodes. The end flag ensures that no further non-None nodes appear, and the function correctly returns true.
  3. Last level partially filled but not left-aligned: If a node is missing on the left but exists on the right at the last level, BFS will encounter None followed by a non-None node. The end flag detects this violation, and the function returns false. This prevents false positives in edge cases with irregular shapes.