How do you solve Count Complete Tree Nodes on LeetCode?

Count Complete Tree Nodes (LeetCode #222) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(log² n) time complexity and O(1) space complexity. Key insight: In a complete binary tree, the last level is filled from left to right, which allows us to use binary search.

What is the brute force solution for Count Complete Tree Nodes?

The brute force approach for Count Complete Tree Nodes is Brute Force, with O(n) time complexity and O(h) space complexity. The simplest way to count nodes in a binary tree is to traverse each node and count them one by one. This is straightforward but inefficient for larger trees. The optimal Optimal Solution approach improves this to O(log² n).

What algorithm or data structure is used to solve Count Complete Tree Nodes?

Count Complete Tree Nodes uses the following concepts: Binary Search, Bit Manipulation, Tree, Binary Tree. The recommended patterns to study are: Binary Search, Tree Traversal.

What are the interview tips for Count Complete Tree Nodes?

Always clarify the properties of the tree before starting your solution. Consider edge cases, such as an empty tree or a tree with only one node. Explain your thought process clearly, especially when transitioning from brute force to optimal solutions.

What are common mistakes when solving Count Complete Tree Nodes?

Not recognizing that the tree is complete, leading to unnecessary full traversals. Failing to account for the last level's structure when counting nodes.

#222

Count Complete Tree Nodes

Easy

Binary SearchBit ManipulationTreeBinary TreeBinary SearchTree Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n)	O(log² n)
Space	O(h)	O(1)

💡

Intuition

Time O(log² n)Space O(1)

Since the tree is complete, we can leverage its properties to count nodes more efficiently using binary search. We can determine the height of the tree and use it to find the number of nodes without visiting each one.

⚙️

Algorithm

3 steps

1Step 1: Calculate the height of the tree by traversing down the leftmost path.
2Step 2: Use binary search to find the last level's rightmost node index, checking if each index exists.
3Step 3: The total number of nodes is calculated as (2^height - 1) + count of valid rightmost nodes.

solution.py44 lines

1class TreeNode:
2    def __init__(self, val=0, left=None, right=None):
3        self.val = val
4        self.left = left
5        self.right = right
6
7class Solution:
8    def countNodes(self, root: TreeNode) -> int:
9        if not root:
10            return 0
11        height = self.getHeight(root)
12        if height == 0:
13            return 1
14        last_level_nodes = self.countLastLevelNodes(root, height)
15        return (1 << height) - 1 + last_level_nodes
16
17    def getHeight(self, node):
18        height = 0
19        while node:
20            height += 1
21            node = node.left
22        return height
23
24    def countLastLevelNodes(self, root, height):
25        left, right = 0, (1 << height) - 1
26        while left < right:
27            mid = (left + right + 1) // 2
28            if self.nodeExists(mid, height, root):
29                left = mid
30            else:
31                right = mid - 1
32        return left + 1
33
34    def nodeExists(self, index, height, node):
35        left, right = 0, (1 << height) - 1
36        for _ in range(height):
37            mid = (left + right) // 2
38            if index <= mid:
39                node = node.left
40                right = mid
41            else:
42                node = node.right
43                left = mid + 1
44        return node is not None

ℹ

Complexity note: The time complexity is O(log² n) because we calculate the height of the tree and perform a binary search for the last level nodes. The space complexity is O(1) since we use a constant amount of space.

1In a complete binary tree, the last level is filled from left to right, which allows us to use binary search.
2The height of the tree can be determined by traversing down the leftmost path.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.