🎨Now live: Try our Free AI Image Generation Feature

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 contributes0
nodes. - Otherwise, we count the node itself plus the nodes in its left and right subtrees.
Approach
- Recursive Function: Define a recursive function
countNodes(root)
that: - Returns0
ifroot
isNone
. - Recursively counts nodes in the left subtree:countNodes(root.left)
. - Recursively counts nodes in the right subtree:countNodes(root.right)
. - Adds1
for the current node. - Base Case: If
root
isNone
, return0
. - 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];
};