Maximum Sum Path from Leaf to Root

Given a binary tree with 'N' nodes, identify the path from a leaf node to the root node that has the maximum sum among all root-to-leaf paths.

Example:

All the possible root to leaf paths are:
3, 4, -2, 4 with sum 9
5, 3, 4 with sum 12
6, 3, 4 with sum 13
Here, the maximum sum is 13. Thus, the output path will be 6, 3, 4.

Input:

The very first line of input contains an integer 'T' denoting the number of queries or test cases.

The first and only line of every test case contains elements of the binary tree in the level order form. The line consists of values of nodes separated by a single space. In case a node is null, we take 0 in its place.

For example, the level order input for the tree depicted in the above image would be :

4
-2 3
4 0 5 6
0 3 0 0 0 0
0 0

Output:

For each test case, print integers representing the path from the leaf node to the root node which has the maximum sum separated by spaces in a single line.

Explanation:

Level 1 :
The root node of the tree is 4

Level 2 :
Left child of 4 = -2
Right child of 4 = 3

Level 3 :
Left child of -2 = 4
Right child of -2 = null (0)
Left child of 3 = 5
Right child of 3 = 6

Level 4 :
Left child of 4 = null (0)
Right child of 4 = 3
Left child of 5 = null (0)
Right child of 5 = null (0)
Left child of 6 = null (0)
Right child of 6 = null (0)

Level 5 :
Left child of 3 = null (0)
Right child of 3 = null (0)

Constraints:

  • 1 <= T <= 100
  • 1 <= N <= 3000
  • -10 ^ 5 <= DATA <= 10 ^ 5, DATA != 0
  • Time limit: 1 sec

Note:

There will be only 1 path with max sum. You do not need to print anything, it has already been taken care of. Just implement the given function.
The above format was just to provide clarity on how the input is formed for a given tree. 
The sequence will be put together in a single line separated by a single space. Hence, for the above-depicted tree, the input will be given as:
4 -2 3 4 0 5 6 0 7 0 0 0 0 0 0
AnswerBot
2mo

Find the maximum sum path from a leaf node to the root in a binary tree using level order input.

  • Input Format: The binary tree is represented in level order, with '0' indicating null nodes.

  • Example: For...read more

Help your peers!
Select
Add answer anonymously...

Popular interview questions of Software Developer Intern

A Software Developer Intern was asked Q1. Buy and Sell Stock Problem Statement Imagine you are Harshad Mehta's friend, and...read more
A Software Developer Intern was asked Q2. Convert Sentence to Pascal Case Given a string STR, your task is to remove space...read more
A Software Developer Intern was asked Q3. Generate Possible Words from T9 Keypad Given a string S consisting of digits fro...read more
EX Squared Solutions Software Developer Intern Interview Questions
Stay ahead in your career. Get AmbitionBox app
play-icon
play-icon
qr-code
Trusted by over 1.5 Crore job seekers to find their right fit company
80 L+

Reviews

10L+

Interviews

4 Cr+

Salaries

1.5 Cr+

Users

Contribute to help millions

Made with ❤️ in India. Trademarks belong to their respective owners. All rights reserved © 2025 Info Edge (India) Ltd.

Follow Us
  • Youtube
  • Instagram
  • LinkedIn
  • Facebook
  • Twitter
Profile Image
Hello, Guest
AmbitionBox Employee Choice Awards 2025
Winners announced!
awards-icon
Contribute to help millions!
Write a review
Write a review
Share interview
Share interview
Contribute salary
Contribute salary
Add office photos
Add office photos
Add office benefits
Add office benefits