222. Count Complete Tree Nodes

Hello, reader 👋🏽 ! Welcome to day 45 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 222. Count Complete Tree Nodes.

🤔 Problem Statement

• Given a complete binary, count and return the number of nodes.

• The algorithm should run in less than O(n).

• E.g.:

  • [1,2,3,4,5,6] => 6
  • [] => 0

💬 Initial Thought Process

• The first solution that would come to your mind is either DFS or BFS traversal. But these traversals take O(n) and since we can do better, I'll not be explaining these two approaches.

💬 Thought Process - Find Height

• The basic idea is to use the fact that the input given is a complete binary tree.
• It is also worth mentioning a trait of perfect binary tree. In a perfect binary tree, all the leaf nodes are in the same level.
  • Hence in a perfect binary tree, the number of nodes is 2^(height) - 1, where height is the height of the tree.
• We can make use of this property to find the number of nodes in a complete binary tree in O(log n * log n) time.
• At every node, we will calculate and compare the right and left subtree height. In doing so, there would be two cases:
  1. If height(root.left) == height(root.right) => the subtree rooted at node root, is a perfect binary tree and the number of nodes in this subtree would be 2^(height) - 1.
  2. If the height(root.left) != height(root.right) => the subtree rooted at node root, is not a perfect binary tree. To calculate the number of nodes in this subtree, we will do the following: 1 + countNodes(root.left) + countNodes(root.right).
     • This means that we will add the current node to the result of number of nodes in the left and right subtree.

👩🏽‍💻 Solution - Find Height

• Below is the code for the DFS approach.

  class Solution {
    public int countNodes(TreeNode root) {
        if(root == null) return 0;
  
        int height = 1;
        TreeNode left = root.left, right = root.right;
  
        while(left != null && right != null) {
            height++;
            left = left.left;
            right = right.right;
        }
  
        if(left == null && right == null) {
            return (int) Math.pow(2, height) - 1;
        }
  
        return 1 + countNodes(root.right) + countNodes(root.left);
    }
  }
  

  Time Complexity: O((log n)^2)
    - n = number of nodes
  Space Complexity: O(log(n))
    - n = number of nodes
        - Auxiliary stack space
  

You can find the link to the GitHub repo for this question here: 222. Count Complete Tree Nodes.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!