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.
1from collections import deque
2
3class TreeNode:
4 def __init__(self, x):
5 self.val = x
6 self.left = None
7 self.right = None
8
9def isCompleteTree(root: TreeNode) -> bool:
10 if not root:
11 return True
12 queue = deque([root])
13 encounteredNull = False
14 while queue:
15 current = queue.popleft()
16 if not current:
17 encounteredNull = True
18 else:
19 if encounteredNull:
20 return False
21 queue.append(current.left)
22 queue.append(current.right)
23 return TrueThe 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.
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#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);
}The C++ approach computes the total nodes and performs a DFS to validate the sequence constraint of a complete binary tree, ensuring node indices fall within an expected range.