interviewing.io

MEDIUM

DATA STRUCTURES AND ALGORITHMS

How to Solve Count Complete Tree Nodes

TREESBINARY TREESSEARCHDEPTH FIRST SEARCH (DFS)

Written By

Hassan Jamous

Tom Wagner

Count Complete Tree Nodes Introduction

The Count Complete Tree Nodes problem asks us to count the number of nodes in a complete binary tree. This problem requires careful consideration of what a complete binary tree is - where every level besides the last is filled in - and the traversal algorithms necessary to explore the tree efficiently.

Count Complete Tree Nodes Problem

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

For this problem a binary tree is considered “complete” if every level besides the last level is completely filled in.

Example Inputs and Outputs

Example 1

Input:

root = [1, 2]

Output: 2

Example 2

Input:

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

Output: 6

Constraints

The number of nodes is less than 10^5.
The input is guaranteed to be a complete binary tree.
Tree size fits in memory.

Practice the Count Complete Tree Nodes Problem With Our AI Interviewer

Start AI Interview

Count Complete Tree Nodes Solutions

Approach 1: Brute Force

When solving an algorithm, it is often best to start with the brute force solution, and from there you can optimize the solution to make it more efficient.

The brute force solution can be achieved by traversing the whole tree and counting the nodes. There are two main methods to traverse a tree, depth-first search (DFS) or breadth-first search (BFS), and each of those methods has pros/cons depending on the problem at hand. However, when the problem simply requires traversing the tree as a whole with no possibility of exiting the traversal early then either approach will work and you can proceed with whatever implementation you are more comfortable coding.

For this problem, let’s use DFS. DFS starts at the root of the tree and explores as deep as possible along each branch before backtracking. DFS can be implemented iteratively or recursively, and for most people both coding out and reading the recursive implementation is easier, so let’s go with the recursive implementation for the purposes of this problem.

# TreeNode definition
# class TreeNode:
#    def __init__(self, data):
#        self.data = data
#        self.left = None
#        self.right = None
 
def count_nodes_dfs(root: TreeNode):
   if root is None:
       return 0
   return count_nodes_dfs(root.left) + count_nodes_dfs(root.right) + 1
# TreeNode definition
# class TreeNode:
#    def __init__(self, data):
#        self.data = data
#        self.left = None
#        self.right = None
 
def count_nodes_dfs(root: TreeNode):
   if root is None:
       return 0
   return count_nodes_dfs(root.left) + count_nodes_dfs(root.right) + 1

Time/Space Complexity

Time complexity: as we are visiting the whole tree, the time complexity will be O(n) where n is the number of nodes.
Space complexity: O(h) where h is the height of the tree. It is not O(1) as the recursive function is using the call stack. As this is a complete binary tree, the height would be FLOOR(log₂n) so space complexity is O(log₂n).

We are making progress. We know the brute force solution, we will communicate it with the interviewer, and we will work on improvements.

Approach 2: Binary Search

Every Level, Except Possibly The Last, Is Completely Filled

We know that in a complete binary tree, every level, except possibly the last, is completely filled. Let’s take the tree below where we have all levels completely filled. Can we think of a way to find the count of all nodes without traversing the whole tree?

Since all the levels are completely filled, we know that level 0 will have 1 node, level 1 will have 2 nodes, level 2 will have 4 nodes, and so on. So, the total number of nodes will be 2^0 + 2^1 + ... + 2^h where h is the height of the tree. This equals to 2^^(h+1) - 1. Which means, in this case, we just need to find the height of the tree to calculate the number of nodes.

This is an interesting and potentially-useful realization: if the tree is completely filled (including the last level), we don't have to traverse the whole tree to know the count. We just need to know the height of the tree. Let’s keep this idea in mind while thinking of a better solution.

Last Level, All Nodes Are As Far Left As Possible

Let’s imagine we are playing a game. We have the complete binary tree below. We do not know which nodes in the last level are filled. Assume you have direct access to the last level’s nodes and you are allowed to reveal any of these nodes. The question is: can you identify which nodes in the last level are filled? Reveal as few nodes as you can. Remember, in a complete binary tree, all nodes are as far left as possible. Take some time to think about it.

One solution is to reveal node A, then B, then C until you reach an empty node. This is a linear search. Can you think of a better way?

We can start by revealing the node in the middle, if it is empty, we therefore know that everything to its right is also empty. From there we continue the search on the left side.

Does this algorithm look familiar? It should – it is binary search! By using this method we are able to make our search faster, as the time complexity would be logarithmic (log(n)) instead of linear (n).

We have a new idea now, binary search; let’s see if we can use it to improve our solution.

Binary Search and Complete Binary Tree

Now, if we are at the root of the tree, and we do not have direct access to the last level, how can we leverage the idea of binary search to find the rightmost node in the last level?

Let’s visualize that. We are at the root, node 1, our goal is to find the rightmost node in the last level. How can we decide if we should go left or right?

Well, we can check the height of the right node, and if it is equal to the height of the current node - 1, this means that there is a path in the right tree where it will take us to a node in the last level. In such a case, we can move to the right and ignore the left tree.

Specific to our example, the current node, node 1, has height = 3 and the right node, node 3, has height = 2. This means we can go right.

We now repeat the same calculation. We are at node 3 and the height of the current node is 2. The height of the right node is 0, not 1, meaning that there is no path to the last level if we go right. So we will ignore the right tree this time and move to the left.

And so on. We will repeat until we reach node 12.

So now that we have a basic algorithm we need to translate that logic to code. For now we will comment out the code related to counting the nodes and focus only on traversing the tree.

# TreeNode definition
# class TreeNode:
#    def __init__(self, data):
#        self.data = data
#        self.left = None
#        self.right = None
 
def calculate_height(node: TreeNode):
   if not node:
       return -1
   height = 0
   while node.left:
       node = node.left
       height += 1
   return height
 
def count_nodes(root: TreeNode):
   nodes_count = 0
   height = calculate_height(root)
 
   while root:
       if calculate_height(root.right) == height - 1:
           # left count statement
           # nodes_count += ??? 
           root = root.right
       else:
           # right count statement
           # nodes_count += ???
           root = root.left
       height -= 1
   return nodes_count
# TreeNode definition
# class TreeNode:
#    def __init__(self, data):
#        self.data = data
#        self.left = None
#        self.right = None
 
def calculate_height(node: TreeNode):
   if not node:
       return -1
   height = 0
   while node.left:
       node = node.left
       height += 1
   return height
 
def count_nodes(root: TreeNode):
   nodes_count = 0
   height = calculate_height(root)
 
   while root:
       if calculate_height(root.right) == height - 1:
           # left count statement
           # nodes_count += ??? 
           root = root.right
       else:
           # right count statement
           # nodes_count += ???
           root = root.left
       height -= 1
   return nodes_count

We have left two commented statements to count the nodes. When we move right, we should count all the nodes to the left. Similarly, when we move left, we should count all the nodes to the right. Can you think of how to do that? Remember what we found here.

When we go right, we know that the tree to the left is completely full, and the height of the left tree is 1 less than the height of the current node.

This means the left count statement will be substituted with the following equation:

nodes_count += pow(2, height)

Using the same logic, when we decide to go left, we know that the tree to the right is full. The height of the right tree will be 2 less than the height of the current node.

This means the right count statement will be substituted with the following equation:

nodes_count += pow(2, height - 1)

Let's add this to the code to arrive at a working implementation for Count Complete Tree Nodes.

# TreeNode definition
# class TreeNode:
#    def __init__(self, data):
#        self.data = data
#        self.left = None
#        self.right = None
 
def calculate_height(node: TreeNode):
   if not node:
       return -1
   height = 0
   while node.left:
       node = node.left
       height += 1
   return height
 
def count_nodes(root: TreeNode):
   nodes_count = 0
   height = calculate_height(root)
 
   while root:
       if calculate_height(root.right) == height - 1:
           nodes_count += pow(2, height) 
           root = root.right
       else:
           nodes_count += pow(2, height - 1) 
           root = root.left
       height -= 1
   return nodes_count
# TreeNode definition
# class TreeNode:
#    def __init__(self, data):
#        self.data = data
#        self.left = None
#        self.right = None
 
def calculate_height(node: TreeNode):
   if not node:
       return -1
   height = 0
   while node.left:
       node = node.left
       height += 1
   return height
 
def count_nodes(root: TreeNode):
   nodes_count = 0
   height = calculate_height(root)
 
   while root:
       if calculate_height(root.right) == height - 1:
           nodes_count += pow(2, height) 
           root = root.right
       else:
           nodes_count += pow(2, height - 1) 
           root = root.left
       height -= 1
   return nodes_count

Time/Space Complexity

Time complexity: The while loop is moving from the root to the last level, Which is h movements, where h is the height of the tree. However, for each iteration of the while loop, we need to calculate the height of the right tree. Remember from the brute-force solution that O(h) is equivalent to O(log₂n), which makes the time complexity O(h^2) or O((log₂n)²), where n is the number of nodes.
Space complexity: We are not using any space for our calculation so space complexity is O(1).

Watch Mock Interviews Featuring the Count Complete Tree Nodes Question

interviewing.io is a mock interview platform, and people in our community routinely share their interview replays to help others get better. In the video below, you can watch people solve Count Complete Tree Nodes. The interview is in Python. The interviewer is an anonymous senior engineer from FAANG.

Amazon InterviewPython Interview

Advance this person to the next round?

Thumbs up

Technical Skills:

4/4

Problem Solving Ability:

4/4

Communication Ability:

4/4

Show Transcript

New Tab

Watch more mock interviews

1

Practice Questions Similar to Count Complete Tree Nodes

Data Structures and Algorithms

Simplify Path

You are given a path to a file as a string. The path can contain the symbols: “..” for the parent directory and “.” for the current directory. Convert the path into its simplified form.

Find Leaves of Binary Tree

Given a binary tree, extract all the leaves in repeated succession into a list of lists by starting at the bottom and working your way upwards.

Data Structures and Algorithms

Reverse String

Write a program to reverse the given string.

About interviewing.io

interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.

Sign up for a mock interview

Interview Problems

We know exactly what to do and say to get the company, title, and salary you want.

Interview prep and job hunting are chaos and pain. We can help. Really.

App screenshot