Why TLE with O(lgn*lgn) solution?


  • 0
    W

    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;
    	}
    }

  • 1
    H

    Try Not using Math.pow() function.


  • 0
    W

    Thank you. That worked.


Log in to reply
 

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