Skip to main content
Talentd

Count Complete Tree Nodes - Solution & Explanation

MediumBinary SearchBit ManipulationTreeBinary Tree26 min readAsked at: Amazon, Microsoft, Meta +4
Practice this problem

Problem Statement

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

According to Wikipedia, every level, except possibly the last, is completely filled in a complete binary tree, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

Design an algorithm that runs in less than O(n) time complexity.

 

Example 1:

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

Example 2:

Input: root = []
Output: 0

Example 3:

Input: root = [1]
Output: 1

 

Constraints:

  • The number of nodes in the tree is in the range [0, 5 * 104].
  • 0 <= Node.val <= 5 * 104
  • The tree is guaranteed to be complete.

Approach Overview

Problem Overview: Given the root of a complete binary tree, return the total number of nodes. A complete tree fills every level from left to right except possibly the last. A naive traversal works, but the structure of a complete tree allows faster counting.

Approach 1: Recursive Height Calculation (O(log² n) time, O(log n) space)

This approach uses the defining property of a complete tree. Compute the height of the leftmost path and the height of the rightmost path. If both heights are equal, the subtree is a perfect binary tree, and the node count is 2^h - 1. If the heights differ, recursively count nodes in the left and right subtrees. Each height calculation takes O(log n) and recursion happens across O(log n) levels, giving overall O(log² n) time with O(log n) recursion stack space.

This method avoids visiting every node. Instead, it repeatedly checks whether a subtree is perfect and skips full sections of the tree. It relies heavily on properties of binary trees and works well when you want a concise recursive solution.

Approach 2: Iterative Binary Search (O(log² n) time, O(1) space)

The last level of a complete tree may be partially filled. Treat the nodes on that level as indices from 0 to 2^h - 1. First compute the tree height by traversing the left edge. Then perform binary search over the index range of the last level to determine how many nodes exist. For each midpoint index, simulate the path from root to that node using bit decisions (left or right). Each existence check costs O(log n), and binary search runs O(log n) steps, producing O(log² n) total time.

This approach keeps memory constant and explicitly leverages the ordered structure of the last level. Bit decisions during traversal resemble operations discussed in bit manipulation, since each bit determines whether to move left or right while navigating the tree.

Recommended for interviews: The recursive height approach is the most common interview answer because it shows you recognize the structural property of complete trees and can reduce work by detecting perfect subtrees. The binary search method demonstrates deeper understanding of indexing the last level and is often considered the optimized conceptual solution.

Approach 1: Approach 1: Recursive Height Calculation

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.

The function countNodes determines the number of nodes in a complete binary tree. It calculates the height of the leftmost path and the rightmost path. If they are equal, it indicates that the tree is a full tree at this level, and the number of nodes is calculated by 2^h - 1.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

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.

Try this approach in the editor →

Approach 2: Approach 2: Iterative Binary Search

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.

The code uses a combination of binary search and tree height properties to find the exact count of nodes. By binary searching the last level of the tree, where nodes might be missing, it logically narrows down potential presence of nodes swiftly.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O((log n)^2) due to binary search depth multiplied by height checks.
Space Complexity: O(1) for iterative implementation.

Try this approach in the editor →

Approach 3: Recursion

We recursively traverse the entire tree and count the number of nodes.

The time complexity is O(n), and the space complexity is O(n), where n is the number of nodes in the tree.

Code

PythonJavaC++GoRustJavaScriptC#

Python

Java

C++

Go

Rust

JavaScript

C#

Try this approach in the editor →

Approach 4: Binary Search

For this problem, we can also take advantage of the characteristics of a complete binary tree to design a faster algorithm.

Characteristics of a complete binary tree: leaf nodes can only appear on the bottom and second-to-bottom layers, and the leaf nodes on the bottom layer are concentrated on the left side of the tree. It should be noted that a full binary tree is definitely a complete binary tree, but a complete binary tree is not necessarily a full binary tree.

If the number of layers in a full binary tree is h, then the total number of nodes is 2^h - 1.

We first count the heights of the left and right subtrees of root, denoted as left and right.

  1. If left = right, it means that the left subtree is a full binary tree, so the total number of nodes in the left subtree is 2^{left} - 1. Plus the root node, it is 2^{left}. Then we recursively count the right subtree.
  2. If left > right, it means that the right subtree is a full binary tree, so the total number of nodes in the right subtree is 2^{right} - 1. Plus the root node, it is 2^{right}. Then we recursively count the left subtree.

The time complexity is O(log^2 n).

Code

PythonJavaC++GoJavaScriptC#

Python

Java

C++

Go

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Recursive Height Calculation

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.

Approach 2: Iterative Binary Search

Time Complexity: O((log n)^2) due to binary search depth multiplied by height checks.
Space Complexity: O(1) for iterative implementation.

Recursion—
Binary Search—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Recursive Height CalculationO(log² n)O(log n)Best general approach for interviews; easy to implement using recursion and subtree height checks.
Iterative Binary Search on Last LevelO(log² n)O(1)Useful when constant extra space is preferred and you want to explicitly exploit the last-level indexing of a complete tree.

Video Solution

Count Complete Tree Nodes | Leetcode #222 • Techdose • 42,673 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Complete Tree Nodes easy or hard?
The problem is labeled Easy on LeetCode because the core idea is recognizing the structure of a complete binary tree. However, discovering the O(log² n) optimization instead of a full traversal can feel closer to a medium-level insight for many candidates.
Count Complete Tree Nodes Python/Java solution
Both Python and Java implementations typically compute subtree heights and apply recursion. The logic checks whether left and right heights are equal to determine if a subtree is perfect. If so, return 2^h - 1; otherwise recursively count nodes in both children.
How to solve Count Complete Tree Nodes in O(n)?
Traverse the tree using DFS or BFS and increment a counter for each visited node. This guarantees correctness for any binary tree and runs in O(n) time with O(h) recursion stack or O(n) queue space depending on the traversal method. It ignores the complete-tree optimization.
What is the best approach for Count Complete Tree Nodes?
The most common solution uses recursive height comparison. Compute the height of the leftmost and rightmost paths. If they match, the subtree is perfect and contains 2^h - 1 nodes. Otherwise recurse on the children. This runs in O(log² n) time because height computation and recursion both take O(log n).
Is Count Complete Tree Nodes asked at Google/Amazon/Meta?
Count Complete Tree Nodes frequently appears in interviews at large tech companies because it tests recognition of structural properties in trees. Instead of brute-force traversal, candidates are expected to detect perfect subtrees or apply binary search on the last level.
What data structure is used in Count Complete Tree Nodes?
The problem uses a binary tree, specifically a complete binary tree. Efficient solutions rely on properties of complete trees, such as predictable height and contiguous node placement on each level, combined with binary search or subtree height calculations.
What is the time complexity of Count Complete Tree Nodes?
The optimized solutions run in O(log² n) time. Each step computes subtree height or performs a node-existence check in O(log n), and the process repeats across O(log n) levels. A simple DFS or BFS traversal would take O(n) time instead.

Ready to solve this problem?

Practice Count Complete Tree Nodes with our built-in code editor and test cases.

Practice on FleetCode
Previous

Closest Binary Search Tree Value