Problem
You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree – it does not have to start at the root.
Examples
Example 1:
|
|
|
|
Solution
Method 1 - Backtracking
To solve this problem, we need to design an algorithm that can find all paths in a binary tree that sum up to a given value. The paths can begin and end at any node in the tree.
Approach
- DFS Traversal: Use Depth-First Search (DFS) to traverse each node.
- Path Tracking: Keep track of the path from the root to the current node.
- Subpath Sums: For each node, check all possible subpaths ending at that node to see if they sum up to the given target value.
- Backtracking: Ensure that after exploring a node, we backtrack to explore other possible paths.
We do DFS with following cases:
- Base case - If the node is null, return.
- Path Tracking: Add the current node to the path.
- Subpath Sums: Iterate backward through the current path and calculate the sum of subpaths ending at the current node. If any subpath sums up to the target, add it to the result.
- Recursive Calls: Recursively explore the left and right subtrees.
- Backtracking: Remove the last node from the current path after exploring both subtrees.
Code
|
|
|
|
Complexity
- ⏰ Time complexity:
O(2^n)
, wheren
is tree size, as in recursion, we split into 2 trees, hence we have to make a choice into 2 branches, hence 2^n. - 🧺 Space complexity:
O(n)
due to the path list and call stack in DFS recursion.