Check completeness of a binary tree
November 6, 2022
treeProblem URL: Check completeness of a binary tree
We will use BFS for level order traversal. We will add children to the BFS queue, if it's a complete tree, we should not have any node once we encounter a null node.
# 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
class Solution:
def isCompleteTree(self, root: Optional[TreeNode]) -> bool:
q = collections.deque([root])
while q:
node = q.pop()
if not node:
break
q.appendleft(node.left)
q.appendleft(node.right)
return not any(q)
Time complexity: O(n)
Space complexity: O(n)