Check Completeness of a Binary Tree

Medium

Trees BFS (Breadth-First Search)Binary Tree Traversal

Problem

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

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 2^h nodes inclusive at the last level h.

Constraints

1 <= number of nodes <= 100
1 <= Node.val <= 1000

Examples

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

Output: true

Every level before the last is full (levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.

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

Output: false

The node with value 7 isn't as far left as possible. There's a gap (null) before node 7 on the last level.

Loading...

Loading Python...