JavaScript O(log²n) time and O(1) space using binary search


  • 0

    Some fantastic solutions posted so far. Here's my attempt:

    var countNodes = function(root) {
        if (!root) return 0;
        let h = depth(root);
        let maxLeaves = 1 << h;
        let low = 0;
        let high = maxLeaves - 1;
        while (low < high) {
            let mid = Math.floor((low + high) / 2);
            if (depth(root, mid, h) === h) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return maxLeaves + low - (depth(root, low, h) < h);
    };
    
    function depth(root, path = 0, max = 0) {
        let h = -1;
        let mask = 1 << max - 1;
        let node = root;
        while (node) {
            h++;
            node = (path & mask) ? node.right : node.left;
            mask >>>= 1;
        }
        return h;
    }
    
    • A complete tree has 2 ** h - 1 nodes plus its bottom-level nodes (h is 0-indexed).
    • We find the number of bottom-level nodes by binary search from 0 to maxLeaves - 1.
    • We can get to the leaves in order by using the binary representation of our search position as a path, where 0 means traverse left and 1 means traverse right. So for a tree with h = 4, 0000 gets to the left-most leaf, 0001 the next leaf, and so on.

    Our time complexity is O(log(max leaves) * (tree height)) = O(h²) or O(log²n) in the number of nodes.


Log in to reply
 

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