Programming Problem: Find All the Root-To-Leaf Paths of a Given Tree

This is one of the series of articles on programming problems. Usually these problems are small and interesting and some arise from simplification of larger problems to make the solution easier to understand and implement.

The problem we are going to solve in this article is as follows: Given a tree

How do we traverse the tree and find all the paths from the root to all the leaves? For this simple tree, we should return the following list: ( [1 2 4], [1 2 5], [1 3] ). Please note that it is actually a list of lists.

For this kind of problems, recursion is the most natural way to solve it once you get the hang of it and notice that any branch of a tree is also a tree. We are to write a function get_all_paths that accepts a root node and returns all the complete paths leading from it. We assume the given tree is well-formed, i.e. not empty. The base case is very simple: For a one-node tree (a leave), we just return ([<root>]) where <root> is the value of the root node. For example, for the tree rooted at 4, we return [(4)].

Now let's see how we can get all the paths leading from the given root. We can easily write a function get_branches that returns the list of all the root nodes of the branches of a given root. For example, the function call get_branches(2) would return (4, 5). For the trees rooted at 4 and 5, calls to the get_branches return the complete paths leading from them. Then we can iterate through all these paths and prepend the current root node to them get the complete paths leading from current root.

Now we can discuss how to implement this in Perl and C++.

Perl implementation

For simplicity, the tree information is hard-coded in the get_branches function. It returns the reference to an array that contains the given node's children (or root nodes of its branches). Its implementation looks like this:

 
sub get_branches
{
	my ($i) = (@_);
	if ($i==1) {
		return [2, 3];
	}
	if ($i==2) {
		return [4, 5, 6];
	}
	...
}

For the get_all_paths function, we decide that it should return the reference to a list of references which contain the complete paths. For example, it should return [ [1, 2, 4], [1, 2, 5], [1, 3] ] for the above sample tree.

Handling the base case is very simple. It just returns a reference to an array which itself contains a reference to a one-node array:

 
$branches = get_branches($root);
if (@$branches == 0) { # we've reached the end/leaf node
	return [ [$root]];
}

Handling the other case is also very simple: We just call the get_all_paths function for each of the branches returned from get_branches and then prepend the root node to all the paths returned earlier.

foreach my $branch (@$branches) {
	my $partial_routes = get_all_paths($branch);
	foreach my $route (@$partial_routes) {
		my @newroute;
		push @newroute, $root;
		push @newroute, @$route;
		push @allroutes, \@newroute;
	}
}

You can download the complete Perl script of traversing all the paths of a tree and try it yourself.

C++ implementation

Once we have a working Perl implementation, it is much easier to implement it with C++. We prefer not to work with pointers, so we choose to use C++ STL's list of list (list<list<int> >) to store all the paths from root to leaves.

To facilitate traversal of a list, we use the Boost's foreach library which make you feel at home if you are used to Perl/PHP's foreach construct.

Since the foreach library provides the BOOST_FOREACH macro and it is a header-only library, you don't need to compile anything to use it. Just include the header file in your code:

 
#include <boost/foreach.hpp>

In your Makefile, you can specify the location of your Boost installation directory and then include it when you compile your program. An example Makefile looks like this:

 
BOOST_ROOT=/var/tmp/omiga/boost_1_40_0
tree: tree.cc
	g++ -I$(BOOST_ROOT) -g -o $@ $<

With the BOOST_FOREACH macro, it is very easy to print all the paths:

 
void print_paths(const list<list<int> >& vv)
{
	BOOST_FOREACH(list<int> v, vv) {	
		BOOST_FOREACH(int i, v) {	
			cout<<i<<" ";
		}
		cout<<"\n";
	}
}

Similar to the above Perl implementation, we can also define the get_branches function as follows:

 
list<int> get_branches(int root)
{
	if (root == 1) {
		int v[] = {2, 3};
		list<int> b(v, v+2);
		return b;
	}
	...
}

Now we are ready to implement the get_all_paths function which can be declared as follows:

list<list<int> > get_all_paths(int root);

Handling the base case of a one-node tree is very simple:

 
branches = get_branches(root);
if (branches.empty()) {
	list<int> v(1, root);
	allpaths.push_back(v);
	return allpaths;
}

When the branches are not empty, we can iterate all the branches. For each branch, we can get all the partial paths from the branch root by calling the get_all_paths function with the branch root and then we can prepend the root node to all the partial paths to get the complete paths. The code looks like this:

BOOST_FOREACH(int b, branches) {
	list<list<int> > partial_paths;
	partial_paths = get_all_paths(b);
	BOOST_FOREACH(list<int> partial_path, partial_paths) {
		partial_path.push_front(root);
		allpaths.push_back(partial_path);
	}
}

You can download the complete C++ program of traversing all the paths of a tree and try it yourself.

Later we will have a separate article to discuss how the traversing of a tree can be used to get all the legitimate jumps for the Checkers game.

Back to articles on development