https://leetcode.com/problems/count-complete-tree-nodes/

countCompleteTreeNodes.js

/*
Idea:
If we know the depth (d) of a full binary tree, we know it has
  - (1 + 2^d) nodes in the layers above the bottom layer
  - Somewhere between 1 and 2^d nodes in the bottom layer

If we let n be the number of nodes, We can guess and check the
number of nodes in the bottom layer in log(n) time.

So do a binary search to count the number of nodes in the bottom
layer. 

Overall TC should be log(n)*log(n), i.e., 
- log(n) to guess and check
- log(n) again, because we guess and check log(n) times
*/
var countNodes = function(root) {
    
    if(!root) return 0;
    
    const getDepth = (node) => node ? (1 + getDepth(node.left)) : 0;
    const d = getDepth(root) - 1;
    
    const nodesAboveBottom = Math.pow(2, d) - 1;
    
    let [min, max, bottomResult] = [1, Math.pow(2, d), 1];
    
    while(min <= max){
        const mid = Math.floor((min+max)/2);
        if(depthExists(mid, root, d)){
            bottomResult = Math.max(bottomResult, mid);
            min = mid+1;
        }else{
            max = mid-1;
        }
    }
    
    return nodesAboveBottom + bottomResult;
};

function depthExists(pos, root, d){
    
    let currentNode = root;
    let currentDepth = 0;
    let [min, max] = [1, Math.pow(2, d)];
    
    while(currentDepth < d){
        let mid = Math.floor((min + max)/2);
        
        if(pos <= mid){
            currentNode = currentNode.left;
            max = mid-1;
        }
        else {
            currentNode = currentNode.right;
            min = mid+1;
        }
        
        if(!currentNode) return false;
        currentDepth++;
    }
    
    return true;
}