TSECAU04 - Editorial

Problem Link:

Practice

Contest

Author: tseccodecell

DIFFICULTY:

Easy

PREREQUISITES:

Level order traversal(BFS)

PROBLEM:

In a complete binary tree, find subtree with maximum level N which has maximum sum of elements.

QUICK EXPLANATION:

We can obtain the sum of sub-tree of the binary tree if we visit each node in the level order traversal or breadth first search.

EXPLANATION:

We can find the maximum sum sub-tree of maximum level n by traversing n-1 levels(or uptil last level of tree) of each node and finding their sum.
Finally the the correct sub-tree is the one having maximum sum for level n.

We store the root node of the maximum sub-tree and finally print the sub-tree once again using level order traversal.

SOLUTION:

https://ideone.com/bUfMGS

1 Like

add editorial for Run Barry Run please

Sorry for the delay, the editorial has been posted.

1 Like

Hi, my code passes 4 out of 6 test cases. Could someone tell me what I am doing wrong or give
any suggestions how to solve it better? Thanks in advance.

Code: [https://www.codechef.com/viewsolution/23878261]