# Binary Search Right Bottom Node Beats 93.5% Python

• When I first met this problem,I tried recursive funtion ,O(nlogn) which is TLE.Then I tried BFS ,O(n),still TLE. At last,I came across the idea of binary search inspired by the binary structure of tree ,which is O(logn)*O(logn). So coool ! I did this all by myself ! It's amazing to share my code with you for the first time ! (Beats 93.5% Python)

``````def bisearch(root,path):
# Store '1'  mains turn left
# Store '0'  mains turn right
left=root.left
right=root.right
if left==None and right==None:
return path
llevel=0
rlevel=0
while left!=None:
left=left.left
llevel+=1
while right!=None:
right=right.left
rlevel+=1
if rlevel<llevel:

return bisearch(root.left,path+[1])
else:
return bisearch(root.right,path+[0])

def countNodes(self, root):
"""
:type root: TreeNode
:rtype: int
"""
#count sum of bottom nodes by the "road"
#then to get the sum of nodes is ez
if root==None:
return 0
left=root.left
llevel=0
while left!=None:
left=left.left
llevel+=1

path=bisearch(root,[])
bottom=0
for j,i in enumerate(path):
if i==1:
continue
else:
bottom+=pow(2,llevel-j-1)
bottom+=1
return pow(2,llevel)-1+bottom``````

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