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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Suppose k is a very large integer(2^64). Which of the following is the largest as n grows to infinity?

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

1from collections import deque  # Import deque, as it's used for the queue.
2
3# Definition for a binary tree node.
4class TreeNode:
5    def __init__(self, value=0, left=None, right=None):
6        self.value = value
7        self.left = left
8        self.right = right
9
10class Solution:
11    def isCompleteTree(self, root: TreeNode) -> bool:
12        # Initialize a queue with the root node to check level by level.
13        nodes_queue = deque([root])
14      
15        # Iterate over the nodes until you find the first None, which signals incomplete level.
16        while nodes_queue:
17            current_node = nodes_queue.popleft()
18          
19            # When a None is encountered, the check for completeness starts.
20            if current_node is None:
21                break
22          
23            # Append left and right children to the queue for further level checking.
24            nodes_queue.append(current_node.left)
25            nodes_queue.append(current_node.right)
26      
27        # At this point, all remaining nodes in the queue should be None for a complete tree.
28        # This loop checks if there is any node that is not None after the first None was found.
29        for node in nodes_queue:
30            if node is not None:
31                return False  # The tree is not complete as there is a node after a None.
32      
33        return True  # The tree is complete as all nodes after the first None are None.
34
35# Example usage:
36# tree = TreeNode(1, TreeNode(2), TreeNode(3))
37# solution = Solution()
38# print(solution.isCompleteTree(tree))  # Output: True
39
1/**
2 * Definition for a binary tree node.
3 */
4class TreeNode {
5    int val;
6    TreeNode left;
7    TreeNode right;
8
9    TreeNode() {}
10
11    TreeNode(int val) {
12        this.val = val;
13    }
14
15    TreeNode(int val, TreeNode left, TreeNode right) {
16        this.val = val;
17        this.left = left;
18        this.right = right;
19    }
20}
21
22class Solution {
23    /**
24     * Determine if a binary tree is complete.
25     * A binary tree is complete if all levels are completely filled except possibly the last,
26     * which is filled from left to right.
27     * 
28     * @param root The root node of the binary tree.
29     * @return true if the tree is complete, false otherwise.
30     */
31    public boolean isCompleteTree(TreeNode root) {
32        // Queue to hold tree nodes for level order traversal
33        Deque<TreeNode> queue = new LinkedList<>();
34        queue.offer(root);
35
36        // Traverse the tree using breadth-first search.
37        // Keep adding children nodes until a null is encountered.
38        while (queue.peek() != null) {
39            TreeNode currentNode = queue.poll();
40            queue.offer(currentNode.left);
41            queue.offer(currentNode.right);
42        }
43
44        // Remove any trailing nulls from the queue.
45        // If any non-null nodes are found afterwards it means that the tree is not complete.
46        while (!queue.isEmpty() && queue.peek() == null) {
47            queue.poll();
48        }
49
50        // If the queue is empty, then all the levels of the tree are fully filled.
51        // Otherwise, the tree is not complete.
52        return queue.isEmpty();
53    }
54}
55
1#include <queue>
2
3// Definition for a binary tree node.
4struct TreeNode {
5    int val;
6    TreeNode *left;
7    TreeNode *right;
8    // Constructor initializes the node with a value, and the left and right pointers as null.
9    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
10    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
11};
12
13class Solution {
14public:
15    // Method to check if a binary tree is complete.
16    bool isCompleteTree(TreeNode* root) {
17        // We use a queue to do a level order traversal of the tree. 
18        std::queue<TreeNode*> nodeQueue;
19        nodeQueue.push(root);
20
21        // Continue level order traversal until we find a null pointer.
22        while (nodeQueue.front() != nullptr) {
23            TreeNode* currentNode = nodeQueue.front();
24            nodeQueue.pop(); // Remove front of the queue after saving the node.
25
26            // Add child nodes to the queue for further processing.
27            nodeQueue.push(currentNode->left);
28            nodeQueue.push(currentNode->right);
29        }
30
31        // After finding the first null pointer, all subsequent nodes must also be null.
32        // Pop all null pointers from the queue.
33        while (!nodeQueue.empty() && nodeQueue.front() == nullptr) {
34            nodeQueue.pop();
35        }
36
37        // If the queue is empty, it means there were no non-null nodes after the first null
38        // which indicates the tree is complete. Otherwise, the tree is not complete.
39        return nodeQueue.empty();
40    }
41};
42
1// Definition for a binary tree node.
2class TreeNode {
3    val: number;
4    left: TreeNode | null;
5    right: TreeNode | null;
6
7    // Constructor initializes the node with a value, and the left and right pointers as null.
8    constructor(val: number, left?: TreeNode | null, right?: TreeNode | null) {
9        this.val = val;
10        this.left = left === undefined ? null : left;
11        this.right = right === undefined ? null : right;
12    }
13}
14
15// Method to check if a binary tree is complete.
16function isCompleteTree(root: TreeNode | null): boolean {
17    if (!root) {
18        // If the root is null, the tree is trivially complete.
19        return true;
20    }
21
22    // We use a queue to do a level order traversal of the tree.
23    const nodeQueue: (TreeNode | null)[] = [root];
24
25    let foundNull = false;
26
27    // Continue level order traversal until the queue is empty.
28    while (nodeQueue.length > 0) {
29        const currentNode = nodeQueue.shift();
30
31        if (!currentNode) {
32            // We encountered a null node; from this point forward, all nodes must be null.
33            foundNull = true;
34        } else {
35            if (foundNull) {
36                // If we previously encountered a null node and now we see a non-null node,
37                // then the tree is not complete.
38                return false;
39            }
40            // Add child nodes to the queue for further processing.
41            nodeQueue.push(currentNode.left);
42            nodeQueue.push(currentNode.right);
43        }
44    }
45
46    // If we finished processing all nodes without finding a non-null
47    // node after a null node, the tree is complete.
48    return true;
49}
50

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.


Fast Track Your Learning with Our Quick Skills Quiz:

How does quick sort divide the problem into subproblems?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Tired of the LeetCode Grind?

Our structured approach teaches you the patterns behind problems, so you can confidently solve any challenge. Get started now to land your dream tech job.

Get Started

🪄