| Question | 222. Count Complete Tree Nodes – Leetcode Javascript Solution |
| Difficulty | Medium |
| Question Type | Tree, Binary Tree |
| Question Link | 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.
According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.
Design an algorithm that runs in less than O(n) time complexity.
Example 1:
Input: root = [1,2,3,4,5,6]
Output: 6Example 2:
Input: root = [1]
Output: 1Example 3:
Input: root = []
Output: 0Constraints:
The number of nodes in the tree is in the range [0, 5 * 104].
0 <= Node.val <= 5 * 104
The tree is guaranteed to be complete.What is Complete Binary Tree?
A complete binary tree is a special type of binary tree where all the levels of the tree are filled completely except the lowest level nodes which are filled from as left as possible.
Solution : ( Using Divide and Conquer approach ) : ==> Optimized
As this is Binary tree, we can simply use Breadth First Search(BFS) or Depth First Search(DFS) to solve this question. But visiting all nodes will take O(n) time complexity. Also, in recursive approach of DFS, will take O(n) as space complexity.
As in question mentioned, given is a complete binary tree. So we can try little trick here. Actually, it only costs h = log(n) time to calculate the height of the tree. ( n is the number of nodes.) So the key point is to calculate what’s the offset of the last element which is in the last row.
So, first we need to find height of the tree. To find height of the tree it will take only log(n) time complexity.
Now we need to find uppercount value by using 2h – 1 forumula, where H is the height of the tree.
once we found uppercount value we need to find bottom of the last row notes nodes. Here we can use divide and conquer technique to find other available notes in the tree.
In Level 3, we need to use divide and conquer to calculate other nodes.
// ------ Divide and conquer Leetcode solution start - jsdiet ------
// using Divide and Conquer
var countNodes = function(root) {
if(!root){
return 0;
}
const height = getTreeHeight(root);
let upperCount = Math.pow(2, height) - 1;
let left =0, right = upperCount;
while(left < right){
let indexToFind = Math.ceil( (left+right)/2 );
if(nodeExists(indexToFind, height, root)){
left = indexToFind;
}else{
right = indexToFind - 1;
}
}
return upperCount + left +1;
};
const getTreeHeight = (node) =>{
let height = 0;
while(node.left){
height++;
node = node.left;
}
return height;
}
const nodeExists = (indexToFind, height, node) => {
let left = 0, right = Math.pow(2, height) - 1, count = 0;
while(count < height){
let mid = Math.ceil((left+right) / 2 );
if(indexToFind >= mid){
node = node.right;
left = mid;
}else{
node = node.left;
right = mid -1;
}
count++;
}
return node !== null;
}
// ------ Divide and conquer Leetcode solution end - jsdiet ------
// Leetcode environment provides already generated binary tree.
// So below part of code no need, if you are trying in Leetcode website environment.
// ------- Code to generate our binary tree -------
// This is purely for testing in local machine
class TreeNode {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
insert(values) {
const queue = [this];
let i = 0;
while (queue.length > 0) {
let current = queue.shift();
for (let side of ["left", "right"]) {
if (!current[side]) {
if (values[i] !== null) {
current[side] = new TreeNode(values[i]);
}
i++;
if (i >= values.length) return this;
}
if (current[side]) queue.push(current[side]);
}
}
return this;
}
}
const tree = new TreeNode(1);
tree.insert([2, 3, null, 5, null, 4]);
// Execute using Divide and Conquer Technique
let val = countNodes(tree);
console.log(val);Complexity Analysis :
Time complexity: O(log(n))
Space complexity: O(1)
Since we are using Divide and Conquer technique our time complexity will become log(n) and space complexity will be O(1) since we are not handingl n number variable storages.
If you have any doubts, add in comment section. Will clarify at my level best. Also, if you have better solution, kindly share it, will grow together as to become better engineer.
