Given a complete binary tree, count the number of nodes.

Note: 

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, 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.

Example:


Input: 
    1
   / \
  2   3
 / \  /
4  5 6

Output: 6

Difficulty: interview

Starter code:

# 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
class Solution:
    def countNodes(self, root: TreeNode) -> int:
        

Solutions:
# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def countNodes(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         node = root
         depth = 0
         while node:
             depth += 1
             node = node.left
         
         if depth <= 1:
             return depth
         
         lo, hi = 0, 2**(depth-2)
         while lo < hi:
             l = depth-3
             mi = (lo+hi)//2
             node = root
             while l >= 0:
                 d = mi & 2**l
                 node = node.right if d > 0 else node.left
                 l -= 1
             if node.left and node.right:
                 lo = mi+1
             elif not node.left and not node.right:
                 hi = mi
             else:
                 break
         l, node = depth-3, root
         while l >= 0:
             d = mi & 2**l
             node = node.right if d > 0 else node.left
             l -= 1
         return 2**(depth-1)-1 + 2*mi + int(node.left is not None) + int(node.right is not None)

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def countNodes1(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         if not root:
             return 0
         if root.left is None and root.right is None:
             return 1
         if root.left is None:
             return 1 + self.countNodes(root.right)
         if root.right is None:
             return 1 + self.countNodes(root.left)
         return 1 + self.countNodes(root.right) + self.countNodes(root.left)
 
     def countNodes(self,root):
         p = root 
         height = 0
         while p:
             height += 1
             p = p.left
         if height <= 1:
             return height
         
         p = root
         while p:
             hr = 0
             pr = p.right
             while pr:
                 hr += 1
                 pr = pr.left
             if hr == height - 1:
                 return 2 ** (height-1) + self.countNodes(p.right)
             return 2 ** (height-2) + self.countNodes(p.left)
             
         
         

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def findHeight(self, node):
         return -1 if node is None else 1 + self.findHeight(node.left)
         
     def countNodes(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         h = self.findHeight(root)
         return 0 if h == -1 else ((1 << h) + self.countNodes(root.right) 
                                   if self.findHeight(root.right) == h-1 else (1 << h-1) + self.countNodes(root.left))

# Definition for a binary tree node.
 # class TreeNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.left = None
 #         self.right = None
 
 class Solution:
     def countNodes(self, root):
         """
         :type root: TreeNode
         :rtype: int
         """
         if not root:
             return 0
         h = height(root)
         res = 0
         while root:
             if height(root.right) == h-1:
                 res += 1<<h
                 root = root.right
             else:
                 res += 1<<(h-1)
                 root = root.left
             h -= 1
             
         return res
 
 def height(node):
     if not node:
         return -1
     else:
         return 1+height(node.left)