New update is available. Click here to update.

Last Updated: 22 Dec, 2020

Difficulty: Moderate

```
Given a binary tree :
```

```
All the root to leaf paths are :
1 2 4
1 2 5
1 3
```

```
1. Two nodes may have the same value associated with it.
2. The root node will be fixed and will be provided in the function.
3. Note that the nodes in a path will appear in a fixed order. For example, 1 2 3 is not the same as 2 1 3.
4. Each path should be returned as a string consisting of nodes in order and separated by a space.
5. The path length may be as small as ‘1’.
```

```
The first line of the input contains a single integer 'T', representing the number of test cases.
The first line of each test case contains an integer 'N', which denotes the number of nodes in the tree.
The second line of each test case will contain the values of the nodes of the tree in the level order form ( -1 for 'NULL' node) Refer to the example for further clarification.
```

```
Consider the binary tree
```

```
The input of the tree depicted in the image above will be like :
1
2 3
4 -1 5 6
-1 7 -1 -1 -1 -1
-1 -1
Explanation :
Level 1 :
The root node of the tree is 1
Level 2 :
Left child of 1 = 2
Right child of 1 = 3
Level 3 :
Left child of 2 = 4
Right child of 2 = null (-1)
Left child of 3 = 5
Right child of 3 = 6
Level 4 :
Left child of 4 = null (-1)
Right child of 4 = 7
Left child of 5 = null (-1)
Right child of 5 = null (-1)
Left child of 6 = null (-1)
Right child of 6 = null (-1)
Level 5 :
Left child of 7 = null (-1)
Right child of 7 = null (-1)
The first not-null node (of the previous level) is treated as the parent of the first two nodes of the current level. The second not-null node (of the previous level) is treated as the parent node for the next two nodes of the current level and so on.
The input ends when all nodes at the last level are null (-1).
```

```
For each test case, print all the root to leaf path nodes.
```

```
You do not need to print anything, it has already been taken care of. Just implement the given function.
```

```
1 <= T <= 10^2
1 <= N <= 3*10^3
Time Limit : 1 sec
```

- We can use a depth-first approach to solve this problem since the tree is a recursive data structure.
- Let us create a recursive function ‘DFS’() which takes the root of the tree and the current string curr for maintaining the current path as the parameter.
- ‘DFS’() traverses the binary tree and stores the root to leaf paths. When we hit a leaf node, we can simply store the current string in some data structure as this string represents a valid root to leaf path
- Now we can return use the ‘RESULT’ list containing all the root to leaf paths in the form of strings.

- In this approach, we use a breadth-first search technique to traverse over all nodes of the binary tree.
- Use a queue (say, ‘BFS’) to store pairs('NODE', ‘CURRENT_PATH’) of the BinaryTreeNode and paths from the root to leaf.
- Use a vector of string (say, ‘RESULT’) to store all the root to leaf paths of the binary tree.
- After storing all the paths as a string, we return this ‘RESULT’ vector.

SIMILAR PROBLEMS

Plantation

Posted: 9 Sep, 2022

Difficulty: Moderate

Capturing Grid

Posted: 14 Sep, 2022

Difficulty: Moderate

The Summit

Posted: 15 Sep, 2022

Difficulty: Easy

Rotting Oranges

Posted: 15 Sep, 2022

Difficulty: Moderate

Distance to a Cycle in Undirected Graph

Posted: 7 Nov, 2022

Difficulty: Moderate

Popular Interview Problems: