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

Given a binary tree, find out the maximum sum of value from root to each leaf.

Objec­tive: - Find the max­i­mum sum leaf to root path in a Binary Tree. Means in all the paths from root to leaves, find the path which has the max­i­mum sum.

Input: A binary tree

Exam­ple:

Maximum-Sum-Leaf-to-Root-path

Maximum-Sum-Leaf-to-Root-path

Approach:

This solu­tion will be divided into two parts

Find the leaf which has the max­i­mum sum from root.

  • Take a global vari­able maxLeaf and max­Sum. (this maxLeaf will the node which has the max­i­mum sum path and max­Sum will the max­i­mum sum.)
  • Do the pre­order traversal
  • At each node, main­tain a another vari­able sum = sum + root.data.
  • When ever you reach to any leaf, check if sum>maxSum, if yes then update the maxLeaf and maxSum.

Print the path from root to that leaf.

Please refer this link to print the path.

Com­plete Code:


Out­put:

Maximum Sum Leaf to Root path :18
Path : 8 6 3 1

You may also like...