O(log^2(n)) using Binary Search, Python, Iterative


  • 3
    Z

    The key idea of this binary search approach is to search in the last level of the tree.

    If the mid of the last level is not None, then the size of last level is at least mid. We keep searching until we find the last not None leaf node, so we can know the size of the last level.

    To get to the Kth node in the last level, I use the binary representation of K to track the path from root to leaf. If current bit is '1' then turn the right child, else turn right.

    def countNodes(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        if root is None:
            return 0
        height = self.getHeight(root)
        last_level = 0
        left, right = 0, 2**height-1
        while left <= right:
            mid = (left+right)/2
            if self.getKthNode(root, height, mid) is None:
                right = mid - 1
            else:
                left = mid + 1
                last_level = mid+1
        return last_level + 2**height - 1
        
    def getHeight(self, root):
        count = 0
        while root.left is not None:
            count += 1
            root = root.left
        return count
        
    def getKthNode(self, root, height, k):
        # binary bits representation of the root-to-leaf path
        while height > 0:
            if 2**(height-1) & k == 2**(height-1): # current bit is '1', turn right
                root = root.right
            else: # current bit is '0', turn left
                root = root.left
            height -= 1
        return root

Log in to reply
 

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