Count Complete Tree Nodes - Medium - L
Published:
Question
- https://leetcode.com/problems/count-complete-tree-nodes/
Given the root of a complete binary tree, return the number of the nodes in the tree.
Approach
- DFS
- Greedy
- Count all right nodes, problem what if the last node in the left subtree? ``` /**
- Definition for a binary tree node.
- struct TreeNode {
- int val;
- TreeNode *left;
- TreeNode *right;
- TreeNode() : val(0), left(nullptr), right(nullptr) {}
- TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
- TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
}; / class Solution { public: int countNodesUtil(TreeNode root, int &h) { if(root==NULL || (root->left==NULL && root->right==NULL)) { return pow(2,h)-1; } if(root->right==NULL) { h = h+1; int val = pow(2, h-2); val = 2*(val-1)+1+pow(2,h-1)-1; return val; } h = h+1; return countNodesUtil(root->right, h); }
int countNodes(TreeNode* root) { if (root==NULL) { return 0; } int h = 1; int val = countNodesUtil(root, h); return val; } }; ```
- Binary search
Solution
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
int get_tree_height(struct TreeNode *root) {
int height = 0;
while(root->left != NULL) {
height++;
root = root->left;
}
return height;
}
bool node_exists(int index_to_find, int height, struct TreeNode *root) {
int left = 0;
int right = pow(2, height) - 1;
int count = 0;
while(count < height) {
int mid_of_node = ceil((float)(left + right)/2);
if(index_to_find >= mid_of_node) {
root = root->right;
left = mid_of_node;
} else {
root = root->left;
right = mid_of_node - 1;
}
count++;
}
return (root != NULL);
}
int countNodes(struct TreeNode* root){
if(root == NULL) {
return 0;
}
int height = get_tree_height(root);
if(height == 0) return 1;
int upper_count = pow(2, height) - 1;
int left = 0;
int right = upper_count;
while(left < right) {
int index_to_find = ceil((float)(left + right)/2);
if(node_exists(index_to_find, height, root)) {
left = index_to_find;
} else {
right = index_to_find - 1;
}
}
return upper_count + left + 1;
}