Problem statement

https://binarysearch.com/problems/Count-Nodes-in-Complete-Binary-Tree/

Solution

Equal to Leetcode 0222. Count Complete Tree Nodes.

Complexity

It is O(log^2 n) for time and space.

Code

class Solution:
    def Path(self, root, num):
        for s in bin(num)[3:]:
            if s == "0": 
                root = root.left
            else:
                root = root.right
            if not root: return False
        return True
        
    def solve(self, root):
        if not root: return 0
        
        left, depth = root, 0
        while left.left:
            left, depth = left.left, depth + 1

        begin, end = (1<<depth), (1<<(depth+1)) - 1
        if self.Path(root,end): return end
        
        while begin + 1 < end:
            mid = (begin + end)//2
            if self.Path(root, mid):
                begin = mid
            else:
                end = mid
        return begin