🎨 Try our Free AI Image Generation Feature

222. Count Complete Tree Nodes

avatar
Dare2Solve

11 months ago

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];
};