Leetcode 222. Count Complete Tree Nodes

Problem Explanation:

This problem is asking to find the number of nodes in the given complete binary tree. A complete binary tree is a binary tree where every level, except possibly the last one, is completely filled. Moreover, all nodes in the last level are as far left as possible.

Note that a node in a binary tree is a structure which contains a value, a reference to the left child, and a reference to the right child. The problem is basically asking us to iterate over all such nodes in the binary tree and count how many we have.

Let's consider an example: Input:

1    1
2 /   \
3 2     3

/ \ /
4 5 6

Output: 6

In this tree, we have 6 nodes which are 1, 2, 3, 4, 5, 6. So, the output is 6.

Solution Explanation:

The solution is using Depth-First Search (DFS) for traversing the tree. This strategy go as deep as possible from the root before visiting the next branch on the same level.

On every node visit, we increment a counter to keep track of the number of nodes in the tree. Then we recursively call the function on the right and left child of the node if they exist.

Let's consider the execution of our solution on the example above. We start from the root node which is '1'. We increment the counter by 1. Then we apply the same process to it's left child (which is '2') and right child (which is '3'). This process will continue untill there are no more nodes to visit. As a result, we will visit all nodes in the tree. Therefore, the function will return the number of nodes in the tree which is our desired output.

Python Solution:

1
2python
3class Solution:
4    def countNodes(self, root):
5        if root is None:
6            return 0
7        else:
8            return 1 + self.countNodes(root.left) + self.countNodes(root.right)

Java Solution:

1
2java
3public class Solution {
4    public int countNodes(TreeNode root) {
5        if (root == null)
6            return 0;
7        else
8            return 1 + countNodes(root.left) + countNodes(root.right);
9    }
10}

JavaScript Solution:

1
2javascript
3class Solution {
4    countNodes(root) {
5        if (root === null)
6            return 0;
7        else
8            return 1 + this.countNodes(root.left) + this.countNodes(root.right);
9    }
10}

C++ Solution:

1
2c++
3class Solution {
4public:
5    int countNodes(TreeNode* root) {
6        if (root == nullptr)
7           return 0;
8        else
9           return 1 + countNodes(root->left) + countNodes(root->right);
10    }
11};

C# Solution:

1
2csharp
3public class Solution {
4    public int CountNodes(TreeNode root) {
5        if (root == null)
6           return 0;
7        else
8           return 1 + CountNodes(root.left) + CountNodes(root.right);
9    }
10}

As it is Depth-First Search, the time complexity is O(n), where n denotes the number of nodes in the tree. One thing to note when implementing this solution is its space complexity. The space complexity of this solution is O(h), where h denotes the height of the tree. This is because the maximum amount of space is used for the recursion stack which will not be greater than the height of the tree.

Although this solution is straightforward and easy to understand, it is not the most efficient one for this specific problem. The solution does a full tree traversal to count each node, but the structure of a complete binary tree can help to make the computation more efficient.

Specifically, in a complete binary tree, all levels except possibly the last are completely filled. This property allows us to use a binary search to find the depth of the tree and the position of the last node in the last level to calculate the total number of nodes directly.

Here is an example of a more efficient Python solution using binary search:

1
2python
3class Solution:
4    def countNodes(self, root):
5        if not root:
6            return 0
7        
8        d = self.depth(root)
9        
10        if d == self.depth(root.right) + 1:
11            return (1 << d) - 1
12        else:
13            return (1 << (d-1)) - 1 + self.countNodes(root.right) + 1
14    
15    def depth(self, root):
16        if not root:
17            return 0
18        else:
19            return 1 + self.depth(root.left)

In this solution, we first calculate the depth of the tree which takes O(log(n)) time. If the depth of the tree root is the same as that of the root's right subtree plus one, it means that the left subtree is a fully complete binary tree, so we add its total node count to the result. Otherwise, the right subtree is a fully complete binary tree with one level less than the main tree, so we add its total node count to the result. This operation also takes O(log(n)) time. Therefore, this solution is an improvement over the DFS solution with a time complexity of O(log(n)^2).