Sponsored
Sponsored
This approach leverages the property of a complete binary tree - where each level, except possibly the last, is completely filled and all nodes are as far left as possible. By loosely calculating the height from root to the leftmost leaf, and rightmost leaf, we can determine if the last level is fully filled and thus decide how to further count nodes efficiently.
Time Complexity: O((log n)^2). This is because we traverse the height multiple times but reducing by the height at each recursive call.
Space Complexity: O(log n) due to the recursive stack space.
1#include <cmath>
2
3int leftHeight(TreeNode* node) {
4 int h = 0;
5 while (node) {
6 h++;
7 node = node->left;
8 }
9 return h;
10}
11
12int rightHeight(TreeNode* node) {
13 int h = 0;
14 while (node) {
15 h++;
16 node = node->right;
17 }
18 return h;
19}
20
21int countNodes(TreeNode* root) {
22 if (!root) return 0;
23 int lh = leftHeight(root);
24 int rh = rightHeight(root);
25 if (lh == rh) return pow(2, lh) - 1;
26 return 1 + countNodes(root->left) + countNodes(root->right);
27}The algorithm takes advantage of complete binary tree properties. If the left and right subtree heights are the same, then it's a perfect binary tree. Otherwise, it divides the problem recursively into subtrees.
The iterative approach adapts a binary search strategy on the last level of the tree, accelerated by the properties of complete trees. It minimizes node checks by directly verifying the presence of nodes via height assessment, thereby pivoting efficiently through the binary search principle.
Time Complexity: O((log n)^2) due to binary search depth multiplied by height checks.
Space Complexity: O(1) for iterative implementation.
1 public int CountNodes(TreeNode root) {
if (root == null) return 0;
int height = GetHeight(root);
int left = 1, right = (1 << (height - 1)), count = right - 1;
while (left < right) {
int mid = (right + left + 1) / 2;
if (NodeExists(mid - 1, height - 1, root)) {
left = mid;
} else {
right = mid - 1;
}
}
return count + left;
}
private int GetHeight(TreeNode node) {
int height = 0;
while (node != null) {
height++;
node = node.left;
}
return height;
}
private bool NodeExists(int idx, int height, TreeNode node) {
int left = 0, right = (1 << (height - 1)) - 1;
for (int i = 0; i < height - 1; ++i) {
int mid = (left + right) / 2;
if (idx <= mid) {
node = node.left;
right = mid;
} else {
node = node.right;
left = mid + 1;
}
}
return node != null;
}
}Utilizing binary search logic, this C# solution uncovers missing nodes on a full-tentative level by methodically probing node existence within presumed intervals.