Purchase Solution

Determining Root-to-Leaf paths equaling the given sum

Not what you're looking for?

Ask Custom Question

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.

Purchase this Solution

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 .

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 ...

Purchase this Solution


Free BrainMass Quizzes
Word 2010: Table of Contents

Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.

Basic Computer Terms

We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.

C++ Operators

This quiz tests a student's knowledge about C++ operators.

Word 2010: Tables

Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.

Basic UNIX commands

Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.