Check Completeness of a Binary Tree in Java

Problem Description

So, you think you can just throw a bunch of nodes together and call it a binary tree? Well, think again! The problem at hand is to determine if a binary tree is “complete.” A complete binary tree is like that overachieving student in class: every level, except possibly the last, is fully filled, and all nodes are as far left as possible. Imagine a tree where the last level is like a party where everyone is crammed to the left side of the room, and no one is standing awkwardly on the right.

In simpler terms, if you have a binary tree, you need to check if it meets the criteria of being complete. If it doesn’t, it’s like showing up to a potluck with just a bag of chips—no one is impressed!

Code Solution

Here’s the Java solution that checks if a binary tree is complete:

Copy Code

class Solution {
  public boolean isCompleteTree(TreeNode root) {
    if (root == null)
      return true;

    Queue q = new LinkedList<>(Arrays.asList(root));

    while (q.peek() != null) {
      TreeNode node = q.poll();
      q.offer(node.left);
      q.offer(node.right);
    }

    while (!q.isEmpty() && q.peek() == null)
      q.poll();

    return q.isEmpty();
  }
}

Approach

The approach taken in this solution is straightforward yet effective. We utilize a queue to perform a level-order traversal of the binary tree. We start by enqueuing the root node. As we dequeue nodes, we enqueue their left and right children. If we encounter a null node, we continue to check if all subsequent nodes are also null. If we find any non-null nodes after a null node, we can confidently declare that the tree is not complete.

Time and Space Complexity

Time Complexity

O(n), where n is the number of nodes in the tree. We traverse each node exactly once.

Space Complexity

O(n) in the worst case, where the queue could store all nodes at the last level of the tree.

Real-World Example

Imagine you’re organizing a family reunion picnic. You have a seating arrangement that needs to be as complete as possible. Everyone should sit at the table, filling in from the left side to the right. If Uncle Bob shows up late and decides to sit at the far right while everyone else is crammed on the left, you’d have a problem. Similarly, a complete binary tree ensures that all nodes are filled from left to right, just like your picnic table should be!