finding path of binary tree from root to leaf.

hello,

I am given a binary tree and I have to print the path from root to leaf nodes .
eg:


5
/ \
4 8
/ / \
11 13 4
/ \ \
7 2 1

Root-to-leaf paths:
path 1: 5 4 11 7
path 2: 5 4 11 2
path 3: 5 8 13
path 4: 5 8 4 1


And also write a function such as
int hasPathSum(struct node* node,int sum)
where sum is the sum of nodes of any path like path1:27,path2:22

which returns true if sum is there in any path and false if not present.

I thought to write the routine as :

//binary tree
struct binarytree
{
int data;
binarytree *left;
binarytree *right;
};
//routine
int hasPathSum(struct node* node,int sum)
{
int count = 0;
while(node != NULL)
{
count += node->data;
node = node->left;
}
if (count == sum)
return 1;
else return 0;
}

But my problem is it is working only for path1 but is it possible to write a generalised way that works for all paths?
My Idea is to do the problem that works for any binary tree not just given above.

Any ideas and code are greatly appreciated.
two lines of code from our book on printing it to a graph
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
template <typename DataType>
inline void BST<DataType>::graph(ostream & out) const
{ graphAux(out, 0, myRoot); }

template <typename DataType>
void BST<DataType>::graphAux(ostream & out, int indent, 
                             BinNodePointer subtreeRoot) const
{
  if (subtreeRoot != 0)
    {
      graphAux(out, indent + 8, subtreeRoot->right);
      out << setw(indent) << " " << subtreeRoot->data << endl;
      graphAux(out, indent + 8, subtreeRoot->left);
    }
}
Hello oonej,

Thanks for your reply, I can't understand the above code since I am a beginner to c++ .could you explain it more briefly or give a more easily understandable solution.
what it does essentially is it takes MyRoot

sends the basic parameters to the graphAux..

within graphAux it takes indent, and pointer of the myroot, then it recursively calls the same function to go down the right side and left side while printing the data while increasing the indent by 8 for each recursion
Last edited on
Topic archived. No new replies allowed.