Sunday, 18 January 2015

Finding the sum of the path of Binary tree in C++ with examples

Finding the sum of the path of Binary tree in Cpp with examples

Let us create a tree as shown below that is a sequence of nodes in the tree starting with the root node to leaf, as we know that leaf node means that node that has no children. And also the empty tree contains no leafs, So there is no possibility of the root-to-leaf paths.

See the below example tree that contains four root-to-leaf paths.

You can see the previous post to insert the data into the binary tree [Explain inserting the data into the Binary Tree in C++ with code examples]
      6

    /    \

  4    12

  /    /    \

10  13  4

/  \     \

8 2    12



The possible Root-to-leaf paths shown below

First path: 6 4 10 8

Second path: 6 4 10 2

Third path: 6 12 13 12

Forth path: 6 12 4

To get the sum of the values of the path is – for example the sum of the above possible paths are
First path: 6 + 4 + 10 + 8 = 28

Second path:  6 + 4 + 10 + 2 = 22

Third path: 6 + 12 + 13 + 12 =  43

Forth path: 6 + 12 + 4 = 22


Given a binary tree and a sum, 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. Return false if no such path can be found.

Function prototype is:
 int FindPathSum(struct node* node, int sum)

Let us see the simple solution for finding the total path of the tree from the root – to - leaf
subtract the node value from the sum when recurring down, and check to see if the sum is 0 when you run out of tree.

int FindPathSum(struct stNode* pstNode, int iTotal) {

if (pstNode == NULL) {

return (iTotal == 0);

}

else {

  int iSubTreeTotal = iTotal - pstNode ->data;

    return (FindPathSum(pstNode ->iLeft, iSubTreeTotal) ||

          FindPathSum (pstNode ->iRight, iSubTreeTotal));
  }

}


No comments: