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

`Input:     1   / \  2   3 / \  /4  5 6Output: 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)`

--

--

10x your algorithm interview prep speed. Take the 5-minute quiz: https://algo.monster/evaluator

Love podcasts or audiobooks? Learn on the go with our new app.

Algo.Monster

10x your algorithm interview prep speed. Take the 5-minute quiz: https://algo.monster/evaluator