Check Completeness of a Binary Tree solution and explanation
Google
9 more videos on this problem
LeetCode Check Completeness of a Binary Tree Explained - JavaNick White · 6:35 · 21K views
Check Completeness of a Binary Tree - Leetcode 958 - PythonNeetCodeIO · 7:57 · 19K views
Check Completeness of a Binary Tree (BFS) - (Meta, Amazon) : Explanation ➕ Live CodingcodestorywithMIK · 12:51 · 19K views
Check Completeness of a Binary Tree (DFS) - (Meta, Amazon) : Explanation ➕ Live CodingcodestorywithMIK · 12:19 · 11K views
Leetcode 958 | Check Completeness of a Binary Tree (Java Solution Explained)The Tech Granth · 7:16 · 3K views
LeetCode 958. Check Completeness of a Binary TreeHappy Coding · 10:12 · 1K views
Check Completeness of a Binary Tree - Leetcode 958 - PythonTechError · 8:21 · 625 views
LeetCode 958 Check Completeness of a Binary TreeJeevan Kumar - Cracckify · 4:16 · 593 views
958. Check Completeness of a Binary Tree | LeetCode daily | C++Priyanshi Porwal · 11:56 · 420 views
958. Check Completeness of a Binary Tree - JAVA (BFS - Detailed explanation)Sourin Majumdar · 8:09 · 368 views
The problem
Given the root of a binary tree, determine if it is a complete binary tree.
In a complete binary tree, every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Example 1:
Input: root = [1,2,3,4,5,6]
Output: true
Explanation: Every level before the last is full (ie. levels with node-values {1} and {2, 3}), and all nodes in the last level ({4, 5, 6}) are as far left as possible.
Example 2:
Input: root = [1,2,3,4,5,null,7] Output: false Explanation: The node with value 7 isn't as far left as possible.
Constraints:
- The number of nodes in the tree is in the range
[1, 100]. 1 <= Node.val <= 1000
Approach overview
Problem Overview: You are given the root of a binary tree and must determine whether the tree is complete. A complete binary tree fills every level from left to right, except possibly the last level where nodes must appear as far left as possible.
Approach 1: Level Order Traversal with Queue (O(n) time, O(n) space)
This approach uses Breadth-First Search to traverse the tree level by level. Push nodes into a queue and process them in order. Once a null node appears during traversal, every node that follows must also be null. If a non-null node appears after a null, the structure violates the left-packed property of a complete binary tree. The key insight is that BFS naturally exposes gaps in the tree structure when scanning level order.
Each node is enqueued once and dequeued once, giving O(n) time complexity and O(n) auxiliary space for the queue in the worst case. This approach is intuitive because completeness is defined based on level order structure.
Approach 2: DFS with Node Counting (O(n) time, O(n) space)
This method relies on indexing nodes the same way an array represents a binary heap. First count the total number of nodes using a DFS traversal of the tree. Then perform another DFS where each node is assigned an index: root = 0, left child = 2*i + 1, right child = 2*i + 2. If any node receives an index greater than or equal to the total node count, the tree cannot be complete.
The insight comes from how complete binary trees map perfectly to array indices with no gaps. A missing internal node causes an index jump beyond the expected range. The traversal visits each node once, so the time complexity is O(n). Recursive DFS requires up to O(h) stack space, which becomes O(n) in the worst case for skewed trees. This approach leverages structural properties of a binary tree and is common in theoretical discussions.
Recommended for interviews: The level order traversal with a queue is the approach most interviewers expect. It directly models the definition of completeness and is easy to reason about during whiteboard discussion. The DFS indexing method demonstrates deeper understanding of tree-to-array mappings and is a strong alternative once you recognize the heap-style indexing property.
Approach 1: Level Order Traversal with Queue
This approach uses a level-order traversal technique with the help of a queue to check if the binary tree is complete. In a complete binary tree, once a null node is encountered while doing a level order traversal, all subsequent nodes must also be null to satisfy completeness.
from collections import deque
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def isCompleteTree(root: TreeNode) -> bool:
if not root:
return True
queue = deque([root])
encounteredNull = False
while queue:
current = queue.popleft()
if not current:
encounteredNull = True
else:
if encounteredNull:
return False
queue.append(current.left)
queue.append(current.right)
return Trueimport java.util.LinkedList;
import java.util.Queue;
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
public boolean isCompleteTree(TreeNode root) {
if (root == null) return true;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean encounteredNull = false;
while (!queue.isEmpty()) {
TreeNode current = queue.poll();
if (current == null) {
encounteredNull = true;
} else {
if (encounteredNull) return false;
queue.offer(current.left);
queue.offer(current.right);
}
}
return true;
}
}#include <iostream>
#include <queue>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
bool isCompleteTree(TreeNode* root) {
if (!root) return true;
std::queue<TreeNode*> q;
q.push(root);
bool encounteredNull = false;
while (!q.empty()) {
TreeNode* current = q.front();
q.pop();
if (!current) {
encounteredNull = true;
} else {
if (encounteredNull) return false;
q.push(current->left);
q.push(current->right);
}
}
return true;
}function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
var isCompleteTree = function(root) {
if (!root) return true;
const queue = [];
queue.push(root);
let encounteredNull = false;
while (queue.length > 0) {
const current = queue.shift();
if (!current) {
encounteredNull = true;
} else {
if (encounteredNull) return false;
queue.push(current.left);
queue.push(current.right);
}
}
return true;
};#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
struct QueueNode {
struct TreeNode* node;
struct QueueNode* next;
};
struct Queue {
struct QueueNode* front;
struct QueueNode* rear;
};
struct Queue* createQueue() {
struct Queue* q = (struct Queue*)malloc(sizeof(struct Queue));
q->front = q->rear = NULL;
return q;
}
void enqueue(struct Queue* q, struct TreeNode* node) {
struct QueueNode* temp = (struct QueueNode*)malloc(sizeof(struct QueueNode));
temp->node = node;
temp->next = NULL;
if (q->rear == NULL) {
q->front = q->rear = temp;
return;
}
q->rear->next = temp;
q->rear = temp;
}
struct TreeNode* dequeue(struct Queue* q) {
if (q->front == NULL)
return NULL;
struct QueueNode* temp = q->front;
q->front = q->front->next;
if (q->front == NULL)
q->rear = NULL;
struct TreeNode* node = temp->node;
free(temp);
return node;
}
bool isQueueEmpty(struct Queue* q) {
return q->front == NULL;
}
bool isCompleteTree(struct TreeNode* root) {
if (root == NULL) return true;
struct Queue* q = createQueue();
enqueue(q, root);
bool encounteredNull = false;
while (!isQueueEmpty(q)) {
struct TreeNode* current = dequeue(q);
if (current == NULL) {
encounteredNull = true;
} else {
if (encounteredNull) return false;
enqueue(q, current->left);
enqueue(q, current->right);
}
}
return true;
}using System;
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
public bool IsCompleteTree(TreeNode root) {
if (root == null) return true;
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
bool encounteredNull = false;
while (queue.Count > 0) {
TreeNode current = queue.Dequeue();
if (current == null) {
encounteredNull = true;
} else {
if (encounteredNull) return false;
queue.Enqueue(current.left);
queue.Enqueue(current.right);
}
}
return true;
}
}The Python solution uses a deque for efficient element removal from the front. Similar to previous implementations, it checks the order of apparitions of null nodes to dictate tree completeness.
Time Complexity: O(n).
Space Complexity: O(n).
Approach 2: DFS with Node Counting
This approach utilizes depth-first search to gather information regarding the number of nodes and their indices. Using these, we check the compactness of the tree at each level to ensure all nodes fit the complete binary tree property.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
def isCompleteTree(root: TreeNode) -> bool:
def countNodes(node):
if not node:
return 0
return 1 + countNodes(node.left) + countNodes(node.right)
def dfs(node, index):
if not node:
return True
if index >= node_count:
return False
return dfs(node.left, 2 * index + 1) and dfs(node.right, 2 * index + 2)
node_count = countNodes(root)
return dfs(root, 0)class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
class Solution {
private int countNodes(TreeNode root) {
if (root == null) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
private boolean dfs(TreeNode node, int index, int nodeCount) {
if (node == null) return true;
if (index >= nodeCount) return false;
return dfs(node.left, 2 * index + 1, nodeCount) && dfs(node.right, 2 * index + 2, nodeCount);
}
public boolean isCompleteTree(TreeNode root) {
int nodeCount = countNodes(root);
return dfs(root, 0, nodeCount);
}
}#include <iostream>
#include <cmath>
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
bool dfs(TreeNode* node, int index, int nodeCount) {
if (node == nullptr) return true;
if (index >= nodeCount) return false;
return dfs(node->left, 2 * index + 1, nodeCount) && dfs(node->right, 2 * index + 2, nodeCount);
}
int countNodes(TreeNode* root) {
if (!root) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
bool isCompleteTree(TreeNode* root) {
int nodeCount = countNodes(root);
return dfs(root, 0, nodeCount);
}function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
function countNodes(root) {
if (!root) return 0;
return 1 + countNodes(root.left) + countNodes(root.right);
}
function dfs(node, index, nodeCount) {
if (!node) return true;
if (index >= nodeCount) return false;
return dfs(node.left, 2 * index + 1, nodeCount) && dfs(node.right, 2 * index + 2, nodeCount);
}
var isCompleteTree = function(root) {
let nodeCount = countNodes(root);
return dfs(root, 0, nodeCount);
};#include <stdio.h>
#include <stdbool.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
bool dfs(struct TreeNode* node, int index, int *nodeCount) {
if (node == NULL) return true;
if (index >= *nodeCount) return false;
return dfs(node->left, 2 * index + 1, nodeCount) && dfs(node->right, 2 * index + 2, nodeCount);
}
int countNodes(struct TreeNode* root) {
if (!root) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
bool isCompleteTree(struct TreeNode* root) {
int nodeCount = countNodes(root);
return dfs(root, 0, &nodeCount);
}using System;
public class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int x) { val = x; }
}
public class Solution {
private int CountNodes(TreeNode root) {
if (root == null) return 0;
return 1 + CountNodes(root.left) + CountNodes(root.right);
}
private bool DFS(TreeNode node, int index, int nodeCount) {
if (node == null) return true;
if (index >= nodeCount) return false;
return DFS(node.left, 2 * index + 1, nodeCount) && DFS(node.right, 2 * index + 2, nodeCount);
}
public bool IsCompleteTree(TreeNode root) {
int nodeCount = CountNodes(root);
return DFS(root, 0, nodeCount);
}
}Python follows the node counting and validating via DFS pattern, ensuring positions fit the expected order of a complete tree.
Time Complexity: O(n).
Space Complexity: O(n), accounting for recursive calls.
Approach 3: Default Approach
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func isCompleteTree(root *TreeNode) bool {
q := []*TreeNode{root}
for q[0] != nil {
root = q[0]
q = q[1:]
q = append(q, root.Left)
q = append(q, root.Right)
}
for len(q) > 0 && q[0] == nil {
q = q[1:]
}
return len(q) == 0
}Complexity comparison
| Approach | Complexity |
|---|---|
| Level Order Traversal with Queue | Time Complexity: O(n). Space Complexity: O(n). |
| DFS with Node Counting | Time Complexity: O(n). Space Complexity: O(n), accounting for recursive calls. |
| Default Approach | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Level Order Traversal with Queue | O(n) | O(n) | Best general solution. Directly verifies completeness using BFS order. |
| DFS with Node Counting and Indexing | O(n) | O(n) | Useful when reasoning about heap-style indexing or validating structural properties. |
Frequently asked questions
Is Check Completeness of a Binary Tree easy or hard?
The problem is generally considered medium difficulty. The concept of a complete binary tree is simple, but recognizing that BFS reveals structural gaps is the key insight. Once that idea is clear, the implementation is straightforward.
Check Completeness of a Binary Tree Python/Java solution
Python and Java implementations typically use a queue for BFS. Enqueue the root, process nodes level by level, and track when a null node appears. If any non-null node is seen after that point, return false; otherwise return true after traversal.
How to solve Check Completeness of a Binary Tree in O(n)?
Use level order traversal with a queue. Push nodes into the queue and process them sequentially. After the first null node is encountered, all remaining nodes must also be null; otherwise the tree violates completeness. Each node is processed once, giving O(n) time complexity.
What is the best approach for Check Completeness of a Binary Tree?
Level order traversal using a queue is the most common solution. Traverse the tree using BFS and once a null node appears, every node after it must also be null. Encountering a non-null node after a null indicates the tree is not complete. The algorithm runs in O(n) time and uses O(n) space.
Is Check Completeness of a Binary Tree asked at Google/Amazon/Meta?
Binary tree structure validation problems frequently appear in interviews at companies like Amazon, Google, and Meta. Variations include checking complete trees, validating heaps, or verifying binary tree properties using BFS or DFS.
What data structure is used in Check Completeness of a Binary Tree?
The most common data structure is a queue used for breadth-first traversal. The queue processes nodes level by level, which makes it easy to detect gaps in the tree. The alternative solution uses recursion and integer indexing during DFS.
What is the time complexity of Check Completeness of a Binary Tree?
The optimal solutions run in O(n) time because each node in the tree is visited exactly once. Both the BFS queue approach and the DFS indexing approach scan every node. Space complexity is O(n) due to the queue in BFS or recursion stack in DFS.