Prerequisites:- Tree, DFS.
Problem :- Given a tree, find the number of leaf nodes using DFS algorithm.
Write the algorithm forming an adjacency list yourself. In the end, output the number of leaf nodes in the tree.
Hint: Leaf nodes are the nodes which do not have any children. You will need to modify your DFS code to count when you encounter a leaf node.
Solution Approach:-
The algorithm uses Depth-First Search (DFS) to explore a tree represented as an adjacency matrix. During the traversal, it counts the number of leaf nodes, which are nodes without any children. The DFS function starts from the root node and recursively explores its children, updating the count whenever it encounters a leaf node. The final count of leaf nodes is then outputted. This approach ensures an efficient way to identify and tally leaf nodes in a tree.
Time Complexity: The time complexity of this approach is O(N+E) = O(N), where N is the number of nodes in the tree, and E is the number of edges.
Space Complexity: O(N)