Dare2Solve
The countNodes
function calculates the total number of nodes in a given binary tree.
To determine the total number of nodes in a binary tree, we can use a recursive approach:
None
, it contributes 0
nodes.Recursive Function: Define a recursive function countNodes(root)
that:
0
if root
is None
.countNodes(root.left)
.countNodes(root.right)
.1
for the current node.Base Case: If root
is None
, return 0
.
Recursive Case: Calculate the total nodes as 1 + countNodes(root.left) + countNodes(root.right)
.
(O(n)), where (n) is the number of nodes in the binary tree. This is because we visit each node exactly once.
(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).
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;
}
};
class Solution:
def countNodes(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return 1 + self.countNodes(root.left) + self.countNodes(root.right)
class Solution {
public int countNodes(TreeNode root) {
if (root == null) {
return 0;
}
return 1 + countNodes(root.left) + countNodes(root.right);
}
}
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];
};