Prerequisites :- Binary Trees, Tree traversal.
Problem :- Given a binary tree and an integer target, retrieve all root-to-leaf paths
where the sum of the node values along the path equals the given integer target.
Print each such path on separate lines.
A root-to-leaf path signifies a path that initiates from the root and concludes
at any leaf node. A leaf node is characterized as a node without any children.
Solution Approach :-
This can be solved by preorder traversal of the given tree. While going down the tree from root,
We keep track of each node and their sum and whenever we reach a leaf node, we check if the running path sum is equal to the target integer or not, if it’s equal, then we add this path to the result vector.
Time complexity: O(N), as we need to visit each nodes at least once.
Space complexity: O(N), as we need to store each node a couple of times while traversing the tree down.