Sponsored
Sponsored
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.
Time Complexity: O(n), where n is the number of nodes in the tree. We traverse each node once.
Space Complexity: O(n), where n is the number of nodes, used for the queue storage.
1function TreeNode(val) {
2 this.val = val;
3 this.left = this.right = null;
4}
5
6var isCompleteTree = function(root) {
7 if (!root) return true;
8 const queue = [];
9 queue.push(root);
10 let encounteredNull = false;
11 while (queue.length > 0) {
12 const current = queue.shift();
13 if (!current) {
14 encounteredNull = true;
15 } else {
16 if (encounteredNull) return false;
17 queue.push(current.left);
18 queue.push(current.right);
19 }
20 }
21 return true;
22};The JavaScript implementation similarly uses an array as a queue substitute. It employs a flag to ensure nodes appear in the expected order to be considered complete.
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.
Time Complexity: O(n).
Space Complexity: O(n), due to recursive stack usage.
1
Python follows the node counting and validating via DFS pattern, ensuring positions fit the expected order of a complete tree.