# Why TLE with O(lgn*lgn) solution?

• I am using binary search in below given solution. Counting height takes logn time. I have an auxiliary function "kthChildExist" which tells whether child number k exists or not at height h, 1 <= k <= 2^h. This function takes logn time.

To get the number of nodes at height h, I do binary search. If kth child exist and (k + 1)th does not, I return k. If either of this condition is false, I change begin and end points accordingly, getting rid of half of the elements each time. This function "lastLevelPopulation" takes logn time.

Overall, O(logn2logn) = O(lgnlgn). However, I still get Time Limit Exceeded for a test case with 1023 nodes. Why is it so? Would appreciate identifying the problem. Below is the code, in Java :-

``````public class Solution {
public int countNodes(TreeNode root) {
if(root == null)
return 0;
int height = height(root);
int nodesAtHeight = lastLevelPopulation(root, height - 1, 1, (int)Math.pow(2, height));
return (int)Math.pow(2, height) - 1 + nodesAtHeight;
}

int lastLevelPopulation(TreeNode root, int power, int begin, int end) {
if(begin >= end)
return end;
int mid = (begin + end) / 2;
if(kthChildExist(root, mid, power)) {
if(!kthChildExist(root, mid + 1, power))
return mid;
else
return lastLevelPopulation(root, power, mid + 2, end);
} else {
return lastLevelPopulation(root, power, begin, mid - 1);
}
}

boolean kthChildExist(TreeNode node, int k, int power) {
if(power == 0) {
if(k == 1)
return node.left != null;
else	// then k must be 2, based on contract
return node.right != null;
}

if(k <= (int)Math.pow(2, power))
return kthChildExist(node.left, k, power - 1);
return kthChildExist(node.right, k - (int)Math.pow(2, power), power - 1);
}

int height(TreeNode root) {
int height = -1;
while(root != null) {
height++;
root = root.left;
}
return height;
}
}``````

• Try Not using Math.pow() function.

• Thank you. That worked.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.