222. Count Complete Tree Nodes

Description:

Given the root of a complete binary tree, return the number of the nodes in the tree.

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

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

'''
[1] naive-recursive solution)

code::
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return self.countNodes(root.left)+self.countNodes(root.right)+1
        
-T/C: O(n)
-S/C: O(h)  # h==floor(logn), height.
'''

'''
[2] efficient solution)

idea::
compare the height of both sub-tree.
if same, can get the number of nodes by Fomula( node # : 2^h-1 )
else, return 1+left-sub+right-sub, 1 for cur_node.

code::
(below)

-T/C: O(h) # h==height of tree, h==logn
-S/C: O(h)
'''

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        l_h, r_h=0,0
        left, right=root,root
        
        while left.left:
            left=left.left
            l_h+=1
        while right.right:
            right=right.right
            r_h+=1
            
        if l_h==r_h:
            return 2**(l_h+1)-1
        
        return 1+self.countNodes(root.left)+self.countNodes(root.right)