Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Print All Paths From Root In a Binary Tree Whose Sum is Equal to a Given Number

Objec­tive: - Given a binary tree and X, Print all the paths start­ing from root so that sum of all the nodes in path equals to a given num­ber.
Exam­ple:

Print All Paths From Root In a Binary Tree Whose Sum is Equal to a Given Number

Approach:

  • Cre­ate a global vari­able as String = path.
  • Do the pre­order
  • if root is greater than Sum required, return.
  • If not then, add root to the path and update the required sum (sum=sum-root.data).
  • if sum required =0, means we have found the path, print it.
  • See the code for bet­ter understanding.

Code:


Out­put:

1 2 7
1 3 6

You may also like...

  • Eugen Daroczy

    By doing the pre­order tra­ver­sal, on the left branch all of the 1, 2, 7 and 5 nodes will be added; is that a valid sce­nario? Since I’m ask­ing I guess that is not a valid path.

    The solu­tion also does not catch the sce­nario where sum = 12. In that con­text, the path would con­sist only of nodes 2, 1, 3 and 6. I’d guess that is a valid path in the tree, right?

    • tuto­ri­al­hori­zon

      Thanks Eugen. It was a solu­tion for some other prob­lem. I have updated the post. Do let me know if you find issues in other posts.