How do you solve Count Complete Tree Nodes?

Compute the left and right heights of the tree. If equal, return 2^height - 1. Otherwise, recursively count nodes in left and right subtrees and add 1 for the root. This approach achieves O((log n)^2) time complexity by reducing the problem size at each recursive call and avoiding full traversal.

Count Complete Tree Nodes

Q: What is the time complexity of Count Complete Tree Nodes?

O((log n)^2). Each recursive call computes the left and right heights in O(log n) time, and the recursion depth is O(log n) because the tree height is logarithmic in the number of nodes. Multiplying these yields O((log n)^2).

Q: What pattern does Count Complete Tree Nodes use?

The Pattern: Binary Search (Height-Based Pruning in Complete Binary Trees) The Heuristic: Exploit the height equality of leftmost and rightmost paths to identify perfect subtrees, enabling O(1) node count calculation and pruning large parts of the tree, thereby reducing the counting problem to a logarithmic number of recursive calls.

Medium Modified Binary Search

Problem

Given the root of a complete binary tree, return the number of the nodes in the tree.

The number of nodes in the tree is in the range [0, 5 * 10⁴]
0 ≤ Node.val ≤ 5 * 10⁴
The tree is guaranteed to be complete.

Example

Input: root = [1,2,3,4,5,6]

Output: 6

The tree is complete, meaning all levels except possibly the last are fully filled, and nodes in the last level are as far left as possible. The algorithm first computes the height of the leftmost path (left height) and the rightmost path (right height). If these heights are equal, the tree is perfect and the number of nodes is 2^height - 1. Otherwise, the algorithm recursively counts nodes in the left and right subtrees and sums them with 1 for the root. This approach avoids traversing every node, improving efficiency.

Approach

Straightforward Solution

A naive approach is to traverse all nodes (e.g., DFS or BFS) and count them, resulting in O(n) time complexity. This is inefficient for large trees.

Core Observation

In a complete binary tree, the leftmost path height and rightmost path height can determine if the tree is perfect (completely filled). If both heights are equal, the number of nodes is known by formula 2^height - 1 without further traversal.

Path to Optimal

Preview

The key insight is to use the properties of a complete binary tree to avoid traversing all nodes. By comparing the leftmost and rightmost heights, the algorithm can identify perfect subtrees and calculate their node counts in O(1) time…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Compute the left and right heights of the tree. If equal, return 2^height - 1…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O((log n)^2)

Each recursive call computes the left and right heights in O(log n) time, and the recursion depth is O(log n) because the tree height is logarithmic in the number of nodes. Multiplying these yields O((log n)^2).

Space

O(log n)

The recursion stack depth is proportional to the height of the tree, which is O(log n) for a complete binary tree. No additional data structures are used.

Pattern Spotlight

Binary Search (Height-Based Pruning in Complete Binary Trees)

Exploit the height equality of leftmost and rightmost paths to identify perfect subtrees, enabling O(1) node count calculation and pruning large parts of the tree, thereby reducing the counting problem to a logarithmic number of recursive calls.

Solution

Python

1class Solution:
  def countNodes(self, root: Optional[TreeNode]) -> int:
      if not root:
          return 0
5
      left = root
      right = root
      left_h = right_h = 0
9
      while left:
          left_h += 1
          left = left.left
13
      while right:
          right_h += 1
          right = right.right
17
      if left_h == right_h:
          return 2 ** left_h - 1
20
      return 1 + self.countNodes(root.left) + self.countNodes(root.right)

Step-by-Step Solution

Handle Empty Tree Edge Case

3if not root:
4    return 0

Objective

To immediately return 0 if the input tree is empty, as there are no nodes to count.

Key Insight

Checking for an empty root node is a critical base case that prevents unnecessary computation and recursion. It defines the boundary condition for the recursive counting process.

Interview Quick-Check

State & Boundaries

Return 0 immediately if the root is None, as an empty tree contains no nodes.

Compute Leftmost and Rightmost Heights to Detect Perfect Subtrees

To calculate the heights of the leftmost and rightmost paths from the root, which determine if the subtree is perfect.

Return Node Count for Perfect Subtrees Using Height Formula

To return the total number of nodes directly when the subtree is perfect, avoiding unnecessary recursion.

Recursively Count Nodes in Imperfect Subtrees

To recursively count nodes in the left and right subtrees when the subtree is not perfect, summing their counts with 1 for the root.

3 more steps with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 19 Critical

return 2 ** left_h - 1

Return node count for perfect subtree using formula 2^height - 1.

This formula leverages the mathematical property of perfect binary trees to compute node count in O(1) time, avoiding traversal.

Line 3 Critical

if not root:

Check if the root node is None (empty tree).

This base case prevents unnecessary recursion and immediately returns 0 for an empty tree, defining the termination condition for the recursion.

Line 18 Critical

if left_h == right_h:

Check if left and right heights are equal.

Equal heights indicate the subtree is perfect, allowing direct calculation of node count without recursion.

Full line-by-line criticality + rationale for all 14 lines available on Pro.

Test Your Understanding

Why does comparing the leftmost and rightmost heights allow us to determine if a subtree is perfect and calculate its node count in O(1)?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Count Complete Tree Nodes from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Count Complete Tree Nodes drill

or drill a free problem

1	`class Solution:`
2	`def countNodes(self, root: Optional[TreeNode]) -> int:`
3	`if not root:`
4	`return 0`
5
6	`left = root`
7	`right = root`
8	`left_h = right_h = 0`
9
10	`while left:`
11	`left_h += 1`
12	`left = left.left`
13
14	`while right:`
15	`right_h += 1`
16	`right = right.right`
17
18	`if left_h == right_h:`
19	`return 2 ** left_h - 1`
20
21	`return 1 + self.countNodes(root.left) + self.countNodes(root.right)`