Katkat
Back

Check if a binary tree is complete

SnapchatSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your understanding of binary tree properties and your ability to perform a level-order traversal to verify structural completeness.

Problem Statement

A binary tree is considered complete if every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible.

Given the root of a binary tree, write a function is_complete(root) that returns True if the tree is complete, and False otherwise.

Function Signature

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def is_complete(root: TreeNode) -> bool:

Examples

Example 1: Input: [1, 2, 3, 4, 5, 6] Output: True Explanation: Every level is filled, and the last level is filled from left to right.

Example 2: Input: [1, 2, 3, 4, 5, None, 7] Output: False Explanation: The node at level 2 is missing a left child, but has a right child, violating the left-alignment rule.

Constraints

  • The number of nodes in the tree is in the range [0, 100].
  • Node values are integers.

Considerations

  • How do you handle empty trees?
  • What happens if you encounter a None node in the middle of your traversal?

Hints

Hint 1

Consider performing a Breadth-First Search (BFS) using a queue to visit nodes level by level.

Hint 2

If you encounter a `None` node during your level-order traversal, all subsequent nodes in the queue must also be `None` for the tree to be complete.

Hint 3

Keep track of whether you have already seen a `None` node; if you find a non-null node after seeing a `None`, return False.

Follow-up questions

  • How would your approach change if you were required to use a Depth-First Search (DFS) approach instead?
  • What is the time and space complexity of your solution in terms of the number of nodes `N`?
  • How would you modify your algorithm to return the height of the tree simultaneously while checking for completeness?