958. Check Completeness of a Binary Tree

Problem Description

In this problem, we are provided with the root node of a binary tree. Our objective is to determine whether the binary tree is a "complete binary tree" or not. A complete binary tree has a few defining characteristics:

• All levels are completely filled, except possibly the last level.
• On the last level, if it’s not completely filled, all the nodes are as far left as possible.

This definition means that in a complete binary tree, if we traverse the nodes level by level from left to right, we will encounter all the non-null nodes first before any null node. If any null nodes are found, there should not be any more non-null nodes after them in this level order traversal.

To sum it up, the task is to check if the given binary tree meets the complete binary tree criteria.

Intuition

To determine if a binary tree is complete, we can perform a level order traversal on the tree. In an ordinary level order traversal (also known as breadth-first search), we enqueue all children of each node and process each node from the left to the right of each level.

The solution is based on an observation that in a complete binary tree, once we encounter the first null node (representing a missing child in the last level or an indication of no more nodes on the last level), all subsequent nodes encountered during the level order traversal must also be null. If we find a non-null node after encountering a null, the tree cannot be considered complete.

Here's the step-by-step reasoning for arriving at the solution:

1. Initiate a queue to perform level order traversal. Start by enqueuing the root node.
2. Begin the level order traversal, dequeuing a node from the front of the queue at each step.
3. Check the current node:
   • If it's not null, enqueue its left and right children (regardless of whether they're null or not) for later processing.
   • If the node is null, this indicates the end of all the non-null nodes encountered so far for the complete binary tree. Any subsequent nodes should be null to ensure the tree is complete.
4. After encountering a null node, check the rest of the queue:
   • If all remaining nodes in the queue are null, the tree is complete.
   • If any non-null node is found, then it's not a complete binary tree.

The algorithm will employ a deque (short for double-ended queue) as it allows efficient insertions and deletions from both ends, which is perfect for our level order traversal needs.

Learn more about Tree, Breadth-First Search and Binary Tree patterns.

Solution Approach

The solution approach implements a level order traversal of the binary tree using a queue data structure. The standard queue is replaced with a deque from Python's collections module for efficient manipulation of the queue's endpoints.

Here's a step-by-step overview of the implementation:

1. Initialize a deque and add the root node of the binary tree to it.

   1q = deque([root])

2. Begin iterating through the queue:

   • For each iteration, dequeue (popleft) an element from the front of the queue.
   • This element represents the current node being processed.

   1while q:
   2    node = q.popleft()

3. The key condition: If the current node is None, it signals that we've encountered a gap in our level order traversal. Break out of the loop as we should not find any more non-null nodes after this point.

   1if node is None:
   2    break

4. If the current node is not None, enqueue its children (left and right) to the back of the queue. These operations will include None values if the current node doesn't have a corresponding child.

   1q.append(node.left)
   2q.append(node.right)

5. After breaking out of the loop, we must verify that all the remaining nodes in the queue are None. This would confirm that we did not encounter any non-null nodes after the first None node, which is a requirement for a complete binary tree.

   1return all(node is None for node in q)

This method relies heavily on the properties of a complete binary tree observed during a level order traversal. By utilizing these properties, the algorithm effectively determines the completeness of the binary tree with an efficient traversal and a simple while loop.

The pattern used in this method is a common Breadth-First Search (BFS) pattern, adapted to check the continuity of node presence at each level of the tree. The presence of a None value in the queue is used as an indicator to signal potential discontinuity, which would imply the binary tree isn't complete. After the first None is seen, the result of the all function confirms whether the rest of the elements left in the queue adhere to the complete binary tree property.

Implementing this approach provides an intuitive and direct method to verify that a binary tree is a complete binary tree. The use of a queue to keep track of nodes for processing and the break condition for encountering None values combine to form an elegant solution for this problem.

Example Walkthrough

Let's assume we have a binary tree structured like this:

1     1
2   /   \
3  2     3
4 / \   /
54   5 6

This binary tree is a complete binary tree because all levels except possibly the last one are fully filled, and all nodes in the last level are as far left as possible.

Now let's walk through the solution approach with this binary tree as an example:

1. We initialize a deque and add the root node of the binary tree (the node with value 1) to it.

   1q = deque([1])

2. We begin iterating through the queue.

   • We dequeue an element from the front of the queue (popleft()), which is the root node with value 1.
   • Since it is not None, we enqueue its children nodes with values 2 and 3.

   1while q:
   2    node = q.popleft()  # node with value 1
   3    q.append(node.left)  # node with value 2
   4    q.append(node.right) # node with value 3

3. Since node with value 1 is not None, we continue with the loop:

   • We again popleft() on the deque, this time getting the node with value 2.
   • We enqueue its children nodes with values 4 and 5.

   1node = q.popleft()  # node with value 2
   2q.append(node.left)  # node with value 4
   3q.append(node.right) # node with value 5

4. We repeat the above step for node with value 3, enqueuing its child with value 6. Since node 3 has no right child, we insert None.

   1node = q.popleft()  # node with value 3
   2q.append(node.left)  # node with value 6
   3q.append(node.right) # None

5. Next, we process nodes 4, 5, and 6. Since they are at the last level and have no children, they would add None values to the queue.

   • Eventually, we encounter the first None value after all nodes on the last level.

   1node = q.popleft()  # node with value 4, adds None values to the queue
   2node = q.popleft()  # node with value 5, adds None values to the queue
   3node = q.popleft()  # node with value 6, adds None values to the queue
   4node = q.popleft()  # None, indicates end of non-null nodes

6. Since we encountered a None, we break out of the loop.

7. Now we check that the rest of the queue only contains None elements. If it does, we confirm that we have a complete binary tree. In this case, all remaining elements are None, so the tree is complete.

   1return all(node is None for node in q)  # returns True, confirming the tree is complete

By following this level order traversal and checking for the first occurrence of None, we have verified the binary tree is complete using our example.

Solution Implementation

Time and Space Complexity

The time complexity of the given code is O(n), where n is the number of nodes in the binary tree. This is because each node is processed exactly once when it is dequeued for examination.

The space complexity of the code is also O(n). In the worst-case scenario, the queue could contain all the nodes at the last level of a complete binary tree, just before the loop terminates upon encountering a None node. This means that the number of elements in the queue could approach the number of leaves in the full binary tree, which is approximately n/2. Considering the constant factor is omitted in Big O notation, the space complexity remains O(n).

Learn more about how to find time and space complexity quickly using problem constraints.