LeetCode 222. Count Complete Tree Nodes. Google interview question.

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

How many nodes does a completely-filled binary tree have

    1
/ \
2 3
/ \ /\
4 5 6 7
# levels = 3# of nodes = 2^3 - 1 = 7
leve 0:      1
/ \
level 1: 2 3
/
level 2: 4
leve 0:      1
/ \
level 1: 2 3
/ \ /
level 2: 4 5 6
class Solution:
def countNodes(self, root):
if not root:
return 0
leftDepth = self.getDepth(root.left)
rightDepth = self.getDepth(root.right)
if leftDepth == rightDepth:
return pow(2, leftDepth) + self.countNodes(root.right) # 2^n -1 + 1 (current node) = 2^n
else:
return pow(2, rightDepth) + self.countNodes(root.left)
def getDepth(self, root):
if not root:
return 0
return 1 + self.getDepth(root.left)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store