Count Complete Tree Nodes https://leetcode.com/problems/count-complete-tree-nodes/?tab=Description
- We need to use the idea of complete tree here.
- Find the left depth (ld) and right depth (rd).
- Only two cases are possible: ld == rd or ld > rd. rd can never be greater than ld because of the manner in which nodes are packed in the last level.
- When ld == rd, then we are sure that left sub-tree is full. The right may or may not be full, but has same depth. Sketch a diagram to get the intuition.
- When ld > rd, then we know that right subtree is full. Sketch a diagram to get the intuition.
- Complexity: O(lgN * lgN) - There are lg(N) steps and in each step we do lg(N) work of finding the depth.
class Solution(object): def depth(self, root): if not root: return 0 return 1 + self.depth(root.left) def countNodes(self, root): """ :type root: TreeNode :rtype: int """ if root == None: return 0 l_d = self.depth(root.left) r_d = self.depth(root.right) if l_d > r_d: return (2**r_d - 1) + self.countNodes(root.left) + 1 else: return (2**l_d - 1) + self.countNodes(root.right) + 1