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:
Input: root = [1,2,3,null,5] Output: ["1->2->5","1->3"]
Example 2:
Input: root = [1] Output: ["1"]
Constraints:
[1, 100].-100 <= Node.val <= 100This approach uses Depth-First Search (DFS) to explore all paths from the root to the leaf nodes. Starting from the root, we recursively visit each node, accumulating the current path. When a leaf node is reached, we add the accumulated path to a list of paths. This can be implemented recursively and is optimal given the constraints.
This C solution uses a recursive DFS function to build the path as a string and store it in an array when a leaf node is reached. - Root value is added to the path for each node and if a leaf is reached, the path is stored in a results array.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the number of nodes in the tree, as we visit each node once.
Space Complexity: O(n), for the space used to store the recursion stack and the result paths.
This approach utilizes an iterative Depth-First Search (DFS) with a stack. By storing the nodes and their paths on the stack, we can simulate the recursive DFS stack. This allows for constructing the paths through iterative backtracking.
This iterative C solution uses a stack to hold nodes and their accumulated paths. When processing each node, its path is updated and child nodes are added to the stack along with updated paths. Leaf nodes are treated as path endpoints.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), traversing each node once.
Space Complexity: O(n), as we maintain a stack proportional to the tree height.
| Approach | Complexity |
|---|---|
| Approach 1: Depth-First Search (DFS) - Recursive | Time Complexity: O(n), where n is the number of nodes in the tree, as we visit each node once. |
| Approach 2: Iterative DFS using a Stack | Time Complexity: O(n), traversing each node once. |
L26. Print Root to Node Path in Binary Tree | C++ | Java • take U forward • 249,457 views views
Watch 9 more video solutions →Practice Binary Tree Paths with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor