# Untitled

unknown
plain_text
a month ago
1.7 kB
2
Indexable
Never
```class Solution:
def compute_depth(self, node: TreeNode) -> int:
"""
Return tree depth in O(d) time.
"""
d = 0
while node.left:
node = node.left
d += 1
return d

def exists(self, idx: int, d: int, node: TreeNode) -> bool:
"""
Last level nodes are enumerated from 0 to 2**d - 1 (left -> right).
Return True if last level node idx exists.
Binary search with O(d) complexity.
"""
left, right = 0, 2**d - 1
for _ in range(d):
pivot = left + (right - left) // 2
if idx <= pivot:
node = node.left
right = pivot
else:
node = node.right
left = pivot + 1
return node is not None

def countNodes(self, root: TreeNode) -> int:
# if the tree is empty
if not root:
return 0

d = self.compute_depth(root)
# if the tree contains 1 node
if d == 0:
return 1

# Last level nodes are enumerated from 0 to 2**d - 1 (left -> right).
# Perform binary search to check how many nodes exist.
left, right = 1, 2**d - 1
while left <= right:
pivot = left + (right - left) // 2
if self.exists(pivot, d, root):
left = pivot + 1
else:
right = pivot - 1

# The tree contains 2**d - 1 nodes on the first (d - 1) levels
# and left nodes on the last level.
return (2**d - 1) + left```