Home » Interview coding problems/challenges

# Count Number of Nodes in a Complete Binary Tree (Leetcode Problem Solution)

In this article, we are going to see **how to find the number of nodes in a complete binary tree efficiently?** This problem has also been featured in the Google interview round.

Submitted by Radib Kar, on August 01, 2020

**Prerequisite:** Complete Binary Tree

**Problem statement:**

Find number of nodes in a complete Binary Tree.

**Examples:**

The above binary Tree is a complete binary tree and has number of **nodes = 4**

**Solution:**

In a **complete binary tree **every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. A **complete Binary Tree** can have between 1 and 2^{h} nodes inclusive at the last level h.

So, the properties of **complete Binary tree** is:

- All levels are filled up except the last level
- The nodes at the last levels are as far left as possible

Now to find the number of nodes we can solve in two ways.

### 1) Naïve approach in O(n)

We can find the number of nodes recursively like for any binary tree.

The number of nodes in the tree= 1+ Number of nodes in the left subtree + Number of nodes in the right subtree. Below is the definition of the recursive function:

int no_of_nodes(TreeNode root){ if (root is NULL) return 0 return 1+ no_of_nodes(root->left)+ no_of_nodes(root->right) }

**C++ Implementation:**

#include <bits/stdc++.h> using namespace std; class TreeNode { public: int val; TreeNode* left; TreeNode* right; TreeNode(int v) { val = v; left = NULL; right = NULL; } }; //calculate number of nodes in //the complete tree recursively int countNodes(TreeNode* root) { if (!root) return 0; return 1 + countNodes(root->left) + countNodes(root->right); } int main() { cout << "Tree which is both complete and full in example 4\n"; TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); cout << "Number of nodes in this tree: " << countNodes(root) << endl; return 0; }

**Output:**

Tree which is both complete and full in example 4 Number of nodes in this tree: 5

### 2) Efficient method using complete binary tree properties

We can count the total number of nodes using complete tree properties:

Say, the total number of nodes is *n*

And the height of the complete binary tree is:** h**

Then it’s guaranteed that all levels up to height h-1 is completed which means has **2 ^{h}-1 number of nodes up to the last level. **At the last level say there r k number of nodes which are as left as much possible. So, we total no of nodes n= k+

**2**

^{h}-1**So, we need to find two things:**

- Height of the tree
- Number of nodes at the last level

Height of the tree can be found in O(Log_{2}n) time and we can find **k also in logarithmic time complexity **using the fact that all the nodes at last level lies as left as far possible.

**The algorithm is like below:**

- If root is NULL return 0
- Compute the height of the tree, h.
- If height is 1 then return 1 (Only root is there)
- As we discussed earlier that all the levels except the last one completed and has 2
^{h}-1 number of nodes. We can compute that in constant time as we already know. Now, we have to calculate number of nodes at the last level,*h*. The number of nodes in the last level can be anything between 1 to 2*k*^{h}. Now to find out exact number of nodes, we perform the binary search like the below implementation by the node index to check how many nodes are in the last level. Say the function iswhich takes number of nodes we expect to be at last level, height of tree and returns true or false. It returns true if the last level has same more nodes that we expected and returns false if the last node has less number of notes than expected. We can find this also in logarithmic time as shown as in the implementation*is_exists***(It's possible because of the fact that all nodes are as left as far possible in the last level for complete binary tree)**. So overall complexity for finding number of nodes is O(logn)*O(logn)

So over all time complexity is O(logn) (to find height and number of nodes in all levels except the last one)+O(logn)^{2}** (**to find number of nodes in the last level

*)***C++ Implementation:**

#include <bits/stdc++.h> using namespace std; class TreeNode { public: int val; TreeNode* left; TreeNode* right; TreeNode(int v) { val = v; left = NULL; right = NULL; } }; bool is_exists(TreeNode* root, int h, int no_of_nodes) { TreeNode* cur = root; int left = 0, right = pow(2, h) - 1; //loop runs for h=O(logn) time //binary search to find the //no_of_nodes th node exist or not for (int i = 0; i < h; ++i) { int mid = left + (right - left) / 2; if (no_of_nodes <= mid) { cur = cur->left; right = mid; } else { cur = cur->right; left = mid + 1; } } //if no_of_nodes at last level exists //then cur will point to that no_of_nodes th node //else NULL return cur != NULL; } //since it's a complete tree we can traverse //towards the left child always //since the last level nodes will be as //left as far possible int height(TreeNode* root) { if (!root) return 0; TreeNode* cur = root; int count = 0; while (cur) { count++; cur = cur->left; } return count; } //calculate number of nodes in //the complete tree efficiently int countNodes(TreeNode* root) { if (!root) return 0; if (!root->left && !root->right) return 1; int h = height(root) - 1; //number of nodes except the last level //is calculated as follow int no_of_nodes_except_last_level = pow(2, h) - 1; //number of possible nodes at the last level int left = 1, right = no_of_nodes_except_last_level; int last_level_nodes; //do binary search to check //if predicted number of node exists or not while (left <= right) { int mid = left + (right - left) / 2; //finds if last level has mid number of nodes or not if (is_exists(root, h, mid)) { left = mid + 1; } else right = mid - 1; } last_level_nodes = left; return no_of_nodes_except_last_level + last_level_nodes; } int main() { cout << "Tree which is both complete and full in example 4\n"; TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); cout << "Number of nodes in this tree: " << countNodes(root) << endl; return 0; }

**Output:**

Tree which is both complete and full in example 4 Number of nodes in this tree: 5

Also tagged in: Google

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.