Explore BrainMass

Explore BrainMass

    Determining Root-to-Leaf paths equaling the given sum

    Not what you're looking for? Search our solutions OR ask your own Custom question.

    This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

    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.

    © BrainMass Inc. brainmass.com March 5, 2021, 12:28 am ad1c9bdddf


    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 .