Why is 2^H - 1 used for a perfect binary tree?

A perfect binary tree contains 1, 2, 4, ... nodes across consecutive levels. For H levels, their sum is 2^H - 1.

Would the height-comparison method work for an arbitrary binary tree?

No. Equal extreme heights do not guarantee that an arbitrary binary tree is perfect. This optimization depends specifically on the input being a complete binary tree.

Why is the optimal approach faster than traversing every node?

Whenever a perfect subtree is detected, its total number of nodes is calculated immediately using 2^H - 1. Every node inside that subtree therefore does not need to be visited individually.

What happens when the tree contains only one node?

Both leftHeight and rightHeight are 1. The tree is therefore treated as perfect, and the formula gives 2¹ - 1 = 1, which is the correct node count.

Count Nodes in a Complete Binary Tree

Given the root of a complete binary tree, determine the total number of nodes present in the tree.

In a complete binary tree:

Every level except possibly the last is completely filled.
Nodes in the last level are placed as far left as possible.

Example 1

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

Output:
6

Explanation:
The binary tree contains a total of 6 nodes.

Example 2

Input:
root = [1]

Output:
1

Explanation:
The tree contains only its root node, so the total number of nodes is 1.

Practice it by yourself before moving onto the solutionTry now

Brute Force Approach

The most direct way to count the nodes is to visit every node once.

For any non-null node, the total number of nodes in its subtree is:

1 + nodes in left subtree + nodes in right subtree

The 1 represents the current node, while the remaining two terms represent the nodes belonging to its left and right subtrees.

This method works for every binary tree and does not make use of the special structure of a complete binary tree. Therefore, even when an entire subtree is perfectly filled and its size could be calculated directly, every node inside it is still visited.

Algorithm

If the current node is null, 0 is returned because no node is present in that subtree.
The number of nodes in the left subtree is recursively calculated.
The number of nodes in the right subtree is recursively calculated.
1 is added for the current node along with the counts obtained from both subtrees.
The resulting count is returned to the parent recursive call.
Once the root has been processed, the returned value represents the total number of nodes in the tree.

Dry Run

Count Nodes in Binary Tree Brute Force Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
5    int val;
6    TreeNode* left;
7    TreeNode* right;
8
9    TreeNode(int value) {
10        val = value;
11        left = nullptr;
12        right = nullptr;
13    }
14};
15
16class Solution {
17public:
18    // Counts every node by recursively
19    // combining the left and right subtree counts.
20    int countNodes(TreeNode* root) {
21        if (root == nullptr) {
22            return 0;
23        }
24
25        int leftCount = countNodes(root->left);
26        int rightCount = countNodes(root->right);
27
28        return 1 + leftCount + rightCount;
29    }
30};
31
32int main() {
33    TreeNode* root = new TreeNode(1);
34    root->left = new TreeNode(2);
35    root->right = new TreeNode(3);
36    root->left->left = new TreeNode(4);
37    root->left->right = new TreeNode(5);
38    root->right->left = new TreeNode(6);
39
40    Solution solution;
41
42    cout << solution.countNodes(root) << endl;
43
44    return 0;
45}

Complexity Analysis

Let N be the number of nodes in the binary tree and H be the height of the tree.

Time Complexity: O(N), where N is the total number of nodes in the binary tree. Every node is visited exactly once.

Space Complexity: O(H), where H is the height of the binary tree, due to the recursion stack. Since the input is a complete binary tree, H = O(log N), so the auxiliary space becomes O(log N).

Optimal Approach

The structure of a complete binary tree can be used to avoid visiting every node.

For each subtree, two heights are calculated:

leftHeight represents the number of nodes encountered while repeatedly moving through left children from the current node.
rightHeight represents the number of nodes encountered while repeatedly moving through right children from the current node.

If leftHeight and rightHeight are equal, the current subtree is a perfect binary tree.

A perfect binary tree with height H, where height represents the number of nodes or levels along the extreme path, contains:

2^H - 1

nodes.

Therefore, when equal heights are found, the entire subtree can be counted immediately without traversing every node inside it.

If the two heights are different, the current subtree is not perfect. Its left and right subtrees are then processed recursively.

Because the original tree is complete, many large subtrees are detected as perfect and counted directly, reducing the amount of traversal required.

Algorithm

If the current node is null, 0 is returned because the subtree contains no nodes.
The value of leftHeight is calculated by repeatedly following left-child pointers from the current node.
The value of rightHeight is calculated by repeatedly following right-child pointers from the current node.
If leftHeight and rightHeight are equal, the subtree is identified as perfect and its node count is calculated directly as 2^leftHeight - 1.
If the two heights are different, the left and right subtrees are recursively processed because the current subtree cannot be counted directly using the perfect-tree formula.
In this case, 1 + countNodes(root->left) + countNodes(root->right) is returned, where 1 represents the current node and the recursive calls count the nodes in both subtrees.

Dry Run

Count Nodes in Binary Tree Optimal Approach Dry Run .png

Solution

1#include <bits/stdc++.h>
2using namespace std;
3
4struct TreeNode {
5    int val;
6    TreeNode* left;
7    TreeNode* right;
8
9    TreeNode(int value) {
10        val = value;
11        left = nullptr;
12        right = nullptr;
13    }
14};
15
16class Solution {
17private:
18    // Measures the extreme left height
19    // of the current subtree.
20    int getLeftHeight(TreeNode* node) {
21        int height = 0;
22
23        // Following only left children gives
24        // the extreme left height of this subtree.
25        while (node != nullptr) {
26            height++;
27            node = node->left;
28        }
29
30        return height;
31    }
32
33    // Measures the extreme right height
34    // of the current subtree.
35    int getRightHeight(TreeNode* node) {
36        int height = 0;
37
38        // Following only right children gives
39        // the extreme right height of this subtree.
40        while (node != nullptr) {
41            height++;
42            node = node->right;
43        }
44
45        return height;
46    }
47
48public:
49    // Uses the complete-tree property to count
50    // perfect subtrees without visiting every node.
51    long long countNodes(TreeNode* root) {
52        if (root == nullptr) {
53            return 0;
54        }
55
56        int leftHeight =
57            getLeftHeight(root);
58
59        int rightHeight =
60            getRightHeight(root);
61
62        // Equal extreme heights mean this complete
63        // subtree is a perfect binary tree.
64        if (leftHeight == rightHeight) {
65
66            // A perfect tree with leftHeight levels has
67            // 2^leftHeight - 1 nodes.
68            // Left shift computes 2^leftHeight.
69            return (1LL << leftHeight) - 1;
70        }
71
72        // When the subtree is not perfect, both sides
73        // are counted recursively along with the root.
74        return 1
75            + countNodes(root->left)
76            + countNodes(root->right);
77    }
78};
79
80int main() {
81    TreeNode* root = new TreeNode(1);
82    root->left = new TreeNode(2);
83    root->right = new TreeNode(3);
84    root->left->left = new TreeNode(4);
85    root->left->right = new TreeNode(5);
86    root->right->left = new TreeNode(6);
87
88    Solution solution;
89
90    cout << solution.countNodes(root) << endl;
91
92    return 0;
93}

Complexity Analysis

Let N be the number of nodes in the complete binary tree and H be its height.

Time Complexity: O(log² N). The height of a complete binary tree is H = O(log N). At each recursive level, up to O(H) work is required to calculate leftHeight and rightHeight, while the recursion proceeds through at most O(H) levels. Therefore, the total time complexity is O(H²) = O(log² N).

Space Complexity: O(log N). The recursion depth is bounded by the height H of the complete binary tree, and H = O(log N).

Interview follow-up Questions

For a complete binary tree, if the extreme left and extreme right paths have the same height, all levels of that subtree must be completely filled. Therefore, the subtree is perfect.

Count Nodes in a Complete Binary Tree

Example 1

Example 2

Brute Force Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Optimal Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Read Similar Blogs

Parent and Distance - Introduction

Flatten Binary Tree to Linked List

Check If a Binary Tree Is a Subtree of Another Tree

Count Nodes in a Complete Binary Tree

Example 1

Example 2

Brute Force Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Optimal Approach

Algorithm

Dry Run

Solution

Complexity Analysis

Interview follow-up Questions

Why does equal left and right height mean the subtree is perfect?

Why is 2^H - 1 used for a perfect binary tree?

Would the height-comparison method work for an arbitrary binary tree?

Why is the optimal approach faster than traversing every node?

What happens when the tree contains only one node?

Read Similar Blogs

Parent and Distance - Introduction

Flatten Binary Tree to Linked List

Check If a Binary Tree Is a Subtree of Another Tree