# Given a binary tree, return all root-to-leaf paths.

Given a binary tree, return all root-to-leaf paths. A leaf is a node with no children.

```Input:

1
/   \
2     3
\
5

Output: ["1->2->5", "1->3"]

Explanation: All root-to-leaf paths are: 1->2->5, 1->3```

Recursive Solution:

```class Solution {
List<String> paths = null;

public List<String> binaryTreePathsRecursive(TreeNode root) {
paths = new ArrayList<>();
constructPath(root, "");
return paths;
}

private void constructPath(TreeNode node, String path) {
if (node == null) return;
path += node.val;
if (node.left == null && node.right == null) {
} else {
path += "->";
constructPath(node.left, path);
constructPath(node.right, path);
}
}
}
```

Time complexity: We visit each node exactly once, thus the time complexity is `O(N)`, where `N` is the number of nodes.

Space complexity: `O(N)`. Here we use the space for a stack call and for a `paths` list to store the answer.  `paths` contains as many elements as leaves in the tree and hence couldn’t be larger than `logN` for the trees containing more than one element. Hence the space complexity is determined by a stack call. In the worst case, when the tree is completely unbalanced, e.g. each node has only one child node, the recursion call would occur `N` times (the height of the tree), therefore the storage to keep the call stack would be `O(N)`. But in the best case (the tree is balanced), the height of the tree would be `logN`. Therefore, the space complexity, in this case, would be `O(log(N))`.

Iterative Solution Using Stack:

```class Solution {
public List<String> binaryTreePaths_1(TreeNode root) {
List<String> paths = new ArrayList<>();
if (root == null) return paths;
String path = null;
while (!nodeStack.isEmpty()) {
TreeNode node = nodeStack.removeLast();
path = pathStack.removeLast();
if (node.left == null && node.right == null) {
}
if (node.left != null) {
}
if (node.right != null) {
}
}
return paths;
}
}
```

Iterative Solution Using Queue:

```class Solution {
public List<String> binaryTreePaths_2(TreeNode root) {
List<String> paths = new ArrayList<>();
if (root == null) return paths;
String path = null;
while (!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.poll();
path = pathQueue.poll();
if (node.left == null && node.right == null) {
}
if (node.left != null) {
}
if (node.right != null) {
• Time complexity: `O(N)` since each node is visited exactly once.
• Space complexity: `O(N)` as we could keep up to the entire tree.