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.
The function countNodes determines the number of nodes in a complete binary tree. It calculates the height of the leftmost path and the rightmost path. If they are equal, it indicates that the tree is a full tree at this level, and the number of nodes is calculated by 2^h - 1.
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#include <stdbool.h>
2
3int countNodes(struct TreeNode* root) {
4 if (!root) return 0;
5
6 int leftHeight(struct TreeNode* node) {
7 int h = 0;
8 while (node) {
9 h++;
10 node = node->left;
11 }
12 return h;
13 }
14
15 int height = leftHeight(root);
16 int start = 1, end = (1 << (height - 1));
17
18 bool nodeExists(int idx, int height, struct TreeNode* node) {
19 int left = 0, right = (1 << (height - 1)) - 1;
20 while (left < right) {
21 int mid = (left + right) / 2;
22 if (idx <= mid) {
23 node = node->left;
24 right = mid;
25 } else {
26 node = node->right;
27 left = mid + 1;
28 }
29 }
30 return node != NULL;
31 }
32
33 int total = (1 << (height - 1)) - 1;
34 while (start < end) {
35 int mid = (start + end + 1) / 2;
36 if (nodeExists(mid-1, height-1, root)) {
37 start = mid;
38 } else {
39 end = mid - 1;
40 }
41 }
42
43 return total + start;
44}The code uses a combination of binary search and tree height properties to find the exact count of nodes. By binary searching the last level of the tree, where nodes might be missing, it logically narrows down potential presence of nodes swiftly.