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 2h nodes inclusive at the last level h.
Example 1:
Input: root = [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: root = [1,2,3,4,5,null,7] Output: false Explanation: The node with value 7 isn't as far left as possible.
Constraints:
[1, 100].1 <= Node.val <= 1000This approach uses a level-order traversal technique with the help of a queue to check if the binary tree is complete. In a complete binary tree, once a null node is encountered while doing a level order traversal, all subsequent nodes must also be null to satisfy completeness.
The C implementation utilizes a custom queue for level-order traversal. We maintain a flag 'encounteredNull' to detect when a null node appears. If any non-null node is found after a null node has been dequeued, we return false immediately, indicating the tree is not complete.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes in the tree. We traverse each node once.
Space Complexity: O(n), where n is the number of nodes, used for the queue storage.
This approach utilizes depth-first search to gather information regarding the number of nodes and their indices. Using these, we check the compactness of the tree at each level to ensure all nodes fit the complete binary tree property.
In C, this solution counts the nodes first, then checks each node for a valid index based on complete tree properties using DFS.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(n), due to recursive stack usage.
| Approach | Complexity |
|---|---|
| Level Order Traversal with Queue | Time Complexity: O(n), where n is the number of nodes in the tree. We traverse each node once. Space Complexity: O(n), where n is the number of nodes, used for the queue storage. |
| DFS with Node Counting | Time Complexity: O(n). Space Complexity: O(n), due to recursive stack usage. |
How to solve (almost) any binary tree coding problem • Inside code • 224,587 views views
Watch 9 more video solutions →Practice Check Completeness of a Binary Tree with our built-in code editor and test cases.
Practice on FleetCode