Binary Tree Paths
Problem Description
Given the root of a binary tree, return all root-to-leaf paths in any order.
A leaf is a node with no children.
Example 1:
Output: ["1->2->5","1->3"]
Example 2:
Input: root = [1]
Output: ["1"]
Constraints:
- The number of nodes in the tree is in the range
[1, 100]. -100 <= Node.val <= 100
Solve it on LeetCode
Approaches
1. Recursive DFS Approach
The recursive DFS approach is straightforward and follows the natural structure of a binary tree. The idea is to start from the root node and explore each path from the root to the leaf nodes. Whenever a leaf node is reached, the path from the root to this leaf node is a completed path and can be stored.
Steps:
- Traverse the tree recursively. Start from the root and keep track of the path.
- If a leaf node is reached (both left and right children are null), the current path is saved.
- Recursively explore both left and right subtrees while updating the current path until all paths are explored.
Code:
- Time Complexity: O(N), where N is the number of nodes in the binary tree, since we visit each node once.
- Space Complexity: O(H), where H is the height of the binary tree due to recursive call stack.
2. Iterative DFS Approach
In this approach, we simulate the behavior of a recursive DFS using an explicit stack. This is useful when recursion depth might be a concern.
Steps:
- Use a stack to manage nodes to be visited along with the path to each node.
- Similar to the recursive approach, but maintain state explicitly using stack operations.
- When a node is a leaf, record its path.
Code:
- Time Complexity: O(N), where N is the number of nodes in the binary tree.
- Space Complexity: O(N), due to the usage of the stack that may store up to N nodes in the worst case.
3. BFS Approach Using a Queue
This approach employs breadth-first traversal using a queue to explore the tree level by level. It applies a similar logic as DFS but tracks paths in parallel for nodes on the same level.
Intuition:
- Traverse using a queue instead of a stack, maintaining the node and its path.
- As each node is processed, add its children (with updated paths) to the traversal queue.
- Whenever a leaf node is encountered, cache its path.
Code:
- Time Complexity: O(N), where N is the number of nodes in the binary tree.
- Space Complexity: O(N), due to the queue which needs to store nodes and their paths.