countNodes

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        def dfs(node, d, mode):
            """
            d: depth; number nodes in path from root to leaf; single node has d=1
            """
            if not node:
                return d
            if mode == 'left':
                return dfs(node.left, d + 1, mode)
            else:
                return dfs(node.right, d + 1, mode)
                
        def follow_path(node, binstr):
            for c in binstr:
                node = node.right if c == '1' else node.left
            return node
                
                
        def bin_search(lo, hi):
            if lo > hi:
                return hi
            mid = lo + (hi - lo) // 2
            b = bin(mid)[2:] # string of 0s and 1s
            b = '0' * (numbits - len(b)) + b
            if follow_path(root, b):
                # search right
                return bin_search(mid + 1, hi)
            else:
                # search left
                return bin_search(lo, mid - 1)
            
        if not root:
            return 0
        hleft = dfs(root, 0, 'left')
        hright = dfs(root, 0, 'right')
        if hleft == hright:
            # a perfect tree
            return 2**hleft - 1
        
        # must count leaves in partial last row
        nodes_above_last_level = 2**hright - 1
        
        max_number_leaves = 2**(hleft - 1)
        lo = 0
        hi = max_number_leaves - 1
        numbits = hleft - 1
        # last_level = 1 <= n < 2**hleft
        # use binary search to find n
        # bin representation of n indicates how to use go from root to leaf n
        nodes_in_last_level = bin_search(lo, hi) + 1
        return nodes_above_last_level + nodes_in_last_level