Explore BrainMass

Determining Root-to-Leaf paths equaling the given sum

A "root-to-leaf path" is defined to be a sequence of nodes in a tree starting with the root node and proceeding downward to a leaf. An empty tree contains no root-to-leaf paths.

My goal, given a binary tree and a sum, is to return true if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum. Returning false if no such path can be found.

There could possibly be more than one root-to-leaf paths for each sum. Find all the root-to-leaf paths that give the required sum.

I have attached a document that can explain what I am trying to do, in detail.


Solution Preview

Please find attached a solution (510301.cpp) to the given problem that has been tested using the attached "tree1Data.txt." Obtained output is pasted below for your reference/cross-checking.

Reading linear binary tree representation from tree1Data.txt ...
Transforming linear ...

Solution Summary

Solution uses a logic that finds all the root-to-leaf paths recursively and on reaching the end of a path it checks if the path sum equals the given sum. Solution code is quite modularized and uses self-explaining names for variables, user defined types, and functions apart from detailed comments.

This solution is aimed at helping you understand how to go about developing a program for the given problem.
Attached program has been tested using GNU C++ compiler g++ version 4.3.4 .