222. Count Complete Tree Nodes

Description

The countNodes function calculates the total number of nodes in a given binary tree.

Intuition

To determine the total number of nodes in a binary tree, we can use a recursive approach:

• If the current node is None, it contributes 0 nodes.
• Otherwise, we count the node itself plus the nodes in its left and right subtrees.

Approach

1. Recursive Function: Define a recursive function countNodes(root) that: - Returns 0 if root is None. - Recursively counts nodes in the left subtree: countNodes(root.left). - Recursively counts nodes in the right subtree: countNodes(root.right). - Adds 1 for the current node.
2. Base Case: If root is None, return 0.
3. Recursive Case: Calculate the total nodes as 1 + countNodes(root.left) + countNodes(root.right).

Complexity

Time Complexity:

(O(n)), where (n) is the number of nodes in the binary tree. This is because we visit each node exactly once.

Space Complexity:

(O(h)), where (h) is the height of the binary tree. This space is used for the recursive call stack. In the worst case, for a skewed tree, (h) could be (n); in the best case of a balanced tree, (h) would be (\log n).

Code

C++

class Solution {
public:
    int countingTraversal(TreeNode* root, int& num) {
        if (root == nullptr) return 0;
        num++;
        countingTraversal(root->left, num);
        countingTraversal(root->right, num);
        return num;
    }
    int countNodes(TreeNode* root) {
        int num = 0;
        countingTraversal(root, num);
        return num;
    }
};

Python

class Solution:
    def countNodes(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + self.countNodes(root.left) + self.countNodes(root.right)

Java

class Solution {
    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + countNodes(root.left) + countNodes(root.right);
    }
}

JavaScript

function countingTraversal(root, num) {
    if (root == null) return;
    else num[0] = num[0] + 1;
    countingTraversal(root.left, num);
    countingTraversal(root.right, num);
};
var countNodes = function (root) {
    let num = [0];
    countingTraversal(root, num);
    return num[0];
};