## Given a binary tree, return all paths from the root to leaves.

The path of all the leafs from a binary tree is processed by traversing the tree and passing the list of Nodes that are higher in the hierarchy. If a node doesn't have children it is a leaf and we store the path in the list of path to return.

This example uses a binary tree with 5 nodes. The root has 2 children, one that is a leaf and the other that has 2 children.

```   1
/ \
2   3
/ \
4   5
```

### Create the following java file:

```import java.util.ArrayList;

public class InterviewPathRootLeaves {

static class Node {
int id;
Node(int id){
this.id = id;
}

Node left;
Node right;
}

public ArrayList<ArrayList<Integer>> getPaths( Node root ){
ArrayList<ArrayList<Integer>> toReturn = new ArrayList<ArrayList<Integer>>();

getPaths( root, new ArrayList<Integer>(), toReturn);

}

public void getPaths( Node root, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> results ){
if( root == null )
return;

// If the node is a leaf
if( root.left == null && root.right == null ){
results.add( new ArrayList<Integer>( path ) );
} else {
getPaths( root.left, path, results );
getPaths( root.right, path, results );
}

// Remove the last element
path.remove( path.size() - 1 );
}

public static void main(String[] argv) throws Exception {

Node root = new Node(1);
root.left = new Node(2);

Node n3 = new Node(3);
root.right = n3;

n3.left  = new Node(4);
n3.right = new Node(5);

InterviewPathRootLeaves s = new InterviewPathRootLeaves();

ArrayList<ArrayList<Integer>> results = s.getPaths( root );
for( ArrayList<Integer> c: results ){
System.out.print("[");
String sep = "";
for( Integer i: c ){
System.out.print( sep + i );
sep = ", ";
}
System.out.println("]");
}
}

}

```

### The output will be:

```[1, 2]
[1, 3, 4]
[1, 3, 5]

```

The algorithm goes through all the nodes recursively. In the example we have 3 leafs, so we have 3 paths stored and rendered in the output.

Binary tree