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);
	
	return toReturn;
    }
    
    public void getPaths( Node root, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> results ){
	if( root == null )
	    return;
	
	path.add( root.id );
	
	// 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.

References:

Binary tree