Prerequisites :- DFS
Problem :- Given an undirected connected tree with N nodes, numbered from 1 to N, and rooted at node 1, along with an integer targetSum, check if there exists a path from root to any leaf whose sum is equal to targetSum.
Solution Approach: This problem can be solved using simple dfs traversal of the given tree. As we start the dfs traversal from the root node, we keep track of current path sum, and as soon as we reach any leaf node (In a general tree, a node is considered a leaf node if it has no children, i.e., it is not a parent to any other nodes.), we check if the current path sum is equal to the given target sum or not. If the sum is equal to the given target sum then we update a boolean flag to true, which was initially set to false.
Time Complexity:
The DFS traversal visits each node and edge once, leading to a time complexity of O(N + E), where N is the number of nodes and E is the number of edges (= N - 1, in case of tree). Hence the overall time complexity is O(N).
Space Complexity:
The space complexity is O(N) for storing the adjacency list and recursion stack during DFS.