Sponsored
Sponsored
This approach leverages the property of a complete binary tree - where each level, except possibly the last, is completely filled and all nodes are as far left as possible. By loosely calculating the height from root to the leftmost leaf, and rightmost leaf, we can determine if the last level is fully filled and thus decide how to further count nodes efficiently.
Time Complexity: O((log n)^2). This is because we traverse the height multiple times but reducing by the height at each recursive call.
Space Complexity: O(log n) due to the recursive stack space.
1class Solution:
2 def left_height(self, node):
3 h = 0
4 while node:
5 h += 1
6 node = node.left
7 return h
8
9 def right_height(self, node):
10 h = 0
11 while node:
12 h += 1
13 node = node.right
14 return h
15
16 def countNodes(self, root):
17 if not root:
18 return 0
19 lh = self.left_height(root)
20 rh = self.right_height(root)
21 if lh == rh:
22 return (1 << lh) - 1
23 return 1 + self.countNodes(root.left) + self.countNodes(root.right)This Python solution calculates the left and right height of the tree from the current node. When the heights are equal, it calculates the perfect node count using bit shifting for efficiency.
The iterative approach adapts a binary search strategy on the last level of the tree, accelerated by the properties of complete trees. It minimizes node checks by directly verifying the presence of nodes via height assessment, thereby pivoting efficiently through the binary search principle.
Time Complexity: O((log n)^2) due to binary search depth multiplied by height checks.
Space Complexity: O(1) for iterative implementation.
1
JavaScript's binary search strategy scrutinizes node presence in potentially incomplete terminal-level nodes, thriftily excluding void nodes promptly.