algoadvance

Leetcode 222. Count Complete Tree Nodes

Problem Statement

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

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

Clarifying Questions

1. Input Constraints:
   • What is the range of the number of nodes in the tree?
   • Can the tree be empty?
2. Output Specification:
   • Do we need to return the result as an integer?
3. Function Signature:
   • What should be the function signature? For example: int countNodes(TreeNode* root)?

Code

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int countNodes(TreeNode* root) {
        if (!root) return 0;

        int left_depth = getDepth(root->left);
        int right_depth = getDepth(root->right);

        if (left_depth == right_depth) {
            return (1 << left_depth) + countNodes(root->right);
        } else {
            return (1 << right_depth) + countNodes(root->left);
        }
    }
    
private:
    int getDepth(TreeNode* node) {
        int depth = 0;
        while (node) {
            depth++;
            node = node->left;
        }
        return depth;
    }
};

Strategy

1. Understanding Complete Binary Tree:
   • In a complete binary tree, the leftmost path gives the maximum depth.
   • Each complete binary tree can be divided into a perfect binary tree and a subtree of another complete binary tree.
2. Recursion Approach:
   • The depth of the left and right subtrees can help decide whether:
     • Left subtree is a perfect binary tree.
     • Right subtree is a perfect binary tree.
   • Using this property allows us to count the nodes efficiently without traversing all nodes.
3. Perfect Binary Tree Nodes:
   • If the left and right subtree depths are the same, then the left subtree is a perfect binary tree.
   • Number of nodes in a perfect binary tree of depth d is 2^d - 1.
4. Counting Nodes:
   • Use the depth information to determine whether the left or right subtree is perfect.
   • Calculate the number of nodes in the perfect subtree using 1 << depth.
   • Recursively count nodes in the subtree that is not perfect.

Time Complexity

• Depth Calculation:
  • Calculating the depth of a subtree takes O(log n) where n is the number of nodes.
• Recursive Traversal:
  • Each recursive step reduces the problem size by approximately half, leading to a logarithmic number of recursive calls.
• Overall:
  • The overall time complexity is O(log^2 n) because at each level of recursion, depth calculation is O(log n) and there are O(log n) levels due to the halving nature of each step.

This approach leverages the properties of complete binary trees to achieve an efficient counting method.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?