In modern software development, algorithms and data structures play a very important role. In particular, one of the problem types that frequently appears in coding tests is tree-related problems. In this article, we will address the problem of counting the number of leaf nodes.
Problem Definition
This is a problem to count the number of leaf nodes in a given binary tree. A leaf node refers to a node that has no children, and considering the properties of a binary tree, a leaf node can have a maximum of two children. This problem will help you practice recursive thinking and tree traversal algorithms.
Problem Description
// Definition of a binary tree node
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}
// Method to count the number of leaf nodes
int countLeafNodes(TreeNode root);
Input: The root node of the binary tree (root).
Output: The number of leaf nodes.
Algorithm Approach
The most common way to find leaf nodes is to traverse the tree and count the nodes that have no children. This problem can be easily solved using a recursive approach.
Recursive Approach
While traversing the tree recursively, perform the following for each node:
- If the current node is null, return 0.
- Check if the current node is a leaf node. (If both left and right children are null)
- If it is a leaf node, return 1; otherwise, respectively count the number of leaf nodes in the left and right subtrees and combine the results.
Implementation
public class Main {
public static void main(String[] args) {
TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
root.right.right = new TreeNode(6);
System.out.println("Number of leaf nodes: " + countLeafNodes(root));
}
public static int countLeafNodes(TreeNode root) {
if (root == null) {
return 0;
}
if (root.left == null && root.right == null) {
return 1;
}
return countLeafNodes(root.left) + countLeafNodes(root.right);
}
}
Example
Let’s assume the binary tree is structured as follows:
1
/ \
2 3
/ \ \
4 5 6
In the above tree, the leaf nodes are 4, 5, and 6, and therefore the number of leaf nodes is 3.
Testing and Validation
To test the implemented method, create several different binary trees and validate the number of leaf nodes. For example, create tests for a tree with 1 node, left/right-skewed trees, and an empty tree.
Test Cases
// Single node tree
TreeNode singleNode = new TreeNode(1);
assert countLeafNodes(singleNode) == 1;
// Empty tree
assert countLeafNodes(null) == 0;
// Left skewed tree
TreeNode leftSkewedTree = new TreeNode(1);
leftSkewedTree.left = new TreeNode(2);
leftSkewedTree.left.left = new TreeNode(3);
assert countLeafNodes(leftSkewedTree) == 1;
// Right skewed tree
TreeNode rightSkewedTree = new TreeNode(1);
rightSkewedTree.right = new TreeNode(2);
rightSkewedTree.right.right = new TreeNode(3);
assert countLeafNodes(rightSkewedTree) == 1;
Complexity Analysis
The time complexity is O(N). We must visit each node once, so N is the number of nodes. The space complexity is O(h), where h is the height of the tree. In the worst case (skewed tree), h can be equal to N.
Conclusion
In this article, we tackled the algorithm problem of counting the number of leaf nodes. I hope this helped you understand recursive thinking and basic binary tree concepts while traversing the tree. While solving algorithm problems, it is essential to always consider how to break down and solve the problem. Practicing with various tree structures is also vital.