Leetcode 958. Check Completeness of a Binary Tree

Related Topic

Breadth-First-Search. Tree.

Description

Given a binary tree, determine if it is a complete binary tree.

Definition of a complete binary tree from Wikipedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Sample I/O

Example 1

Input: [1,2,3,4,5,6]
Output: true
Explanation: 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: [1,2,3,4,5,null,7]
Output: false
Explanation: The node with value 7 isn't as far left as possible.

Note

The tree will have between 1 and 100 nodes.

Methodology

This question can be solved by Breadth First Search.

A complete binary tree is a tree each level has to be fully filled except the last level, all nodes in the last level has to be as far left as possible. For each level that fully filled with nodes, the number of nodes are satify the formula 2^(n-1) where n is the level that start from 1.

For this question, we need to check if all level except last level has the right number of nodes. After that we need to check if there is null before last node in last level.

Note if there is not root node, return True

Code

def isCompleteTree(self, root: TreeNode) -> bool:
    if root is None: return True
    res = []
    q = collections.deque([(root,1)])
    while q:
        root, pos = q.popleft()
        res.append(pos)
        if root.left:
            q.append((root.left, 2*pos))
        if root.right:
            q.append((root.right, 2*pos+1))
    return len(res) == res[-1]

BigO

We go through all nodes once, so the total time complexity is O(n)