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.
1#include <iostream>
2#include <queue>
3
4struct TreeNode {
5 int val;
6 TreeNode *left;
7 TreeNode *right;
8 TreeNode(int x) : val(x), left(NULL), right(NULL) {}
9};
10
11bool isCompleteTree(TreeNode* root) {
12 if (!root) return true;
13 std::queue<TreeNode*> q;
14 q.push(root);
15 bool encounteredNull = false;
16 while (!q.empty()) {
17 TreeNode* current = q.front();
18 q.pop();
19 if (!current) {
20 encounteredNull = true;
21 } else {
22 if (encounteredNull) return false;
23 q.push(current->left);
24 q.push(current->right);
25 }
26 }
27 return true;
28}In C++, the solution employs the standard library queue to process nodes level-wise. Using the 'encounteredNull' flag, we ensure all levels before the last are full, and any nodes after a null are not permissible, ensuring 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
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);
}
}C# employs recursive calls to count nodes and check each node's index, ensuring a consecutive sequence aligning with that of a complete binary tree.