Compute sums and maximum path in a tree

Q: Compute sums and maximum path in a tree

This question evaluates understanding and implementation of binary tree traversal, recursion, aggregation of node values, and computation of maximum simple-path sums, measuring competency in data structures and algorithmic problem-solving within the Coding & Algorithms domain.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

You are given a binary tree whose nodes store integer values. You must implement your own Node class (e.g., val, left, right).

Task

Write a function that, given the root node, computes all of the following:

Total sum : the sum of values of all nodes in the tree.
Maximum path value : the maximum possible sum of values along a simple path in the tree, where a path:
- can start and end at any two nodes,
- must follow parent-child links,
- cannot visit a node more than once.
Nodes on a maximum path : return one valid path (as a list of node values, or node references) that achieves the maximum path value.

Input / Output

Input: root (or null for an empty tree).
Output: a structure/tuple like (totalSum, maxPathSum, maxPathNodes) .

Constraints (assume)

0 <= number of nodes <= 2e5
Node values are integers (may be negative).

Notes

If the tree is empty, define totalSum = 0 , maxPathSum = 0 , and maxPathNodes = [] .
If multiple maximum paths exist, returning any one is acceptable.

Compute sums and maximum path in a tree

Quick Overview

Task

Input / Output

Constraints (assume)

Notes

Comments (0)