Compute maximum path sum in a binary tree

Q: Compute maximum path sum in a binary tree

This question evaluates understanding of binary tree data structures and algorithmic competency for computing path-based aggregates, encompassing recursion, tree traversal, and handling of positive and negative node values.

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.

Q: What difficulty level is this interview question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at TikTok.

Q: What role is this question designed for?

This question is commonly asked for Software Engineer candidates at TikTok during technical interviews.

Question

You are given the root of a binary tree where each node contains an integer value (which may be positive, zero, or negative).

A path in the tree is defined as any sequence of nodes such that:

Each pair of consecutive nodes in the sequence is connected by an edge in the tree.
A path may start and end at any nodes in the tree.
A path must contain at least one node.
The path cannot reuse the same node more than once (i.e., it is a simple path; it does not branch or form cycles).

The path sum is the sum of the node values along that path.

Task

Implement a function that returns the maximum path sum over all possible paths in the tree.

Function Signature

You can assume a typical binary tree node definition, for example in a C++/Java-like style:

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

Write a function:

int maxPathSum(TreeNode root)

which returns the maximum path sum.

Constraints

The number of nodes in the tree is in the range [1, 3 * 10^4].
Each node value is in the range [-10^3, 10^3].
The tree is not necessarily balanced.

Examples

Example 1

Input tree (level-order representation): [1, 2, 3]

This corresponds to the structure:

    1
   / \
  2   3

All possible simple paths and their sums:

2 → 1 → 3 has sum 2 + 1 + 3 = 6
2 → 1 has sum 3
1 → 3 has sum 4
Single-node paths: 2, 1, 3

Output: 6

Example 2

Input tree (level-order): [-10, 9, 20, null, null, 15, 7]

Structure:

The maximum path is 15 → 20 → 7 with sum 15 + 20 + 7 = 42.

Output: 42

Example 3

Input tree (single node): [-3]

Only one possible path: the single node itself.

Output: -3

Notes

The maximum path is allowed to start and end at any two nodes in the tree.
The path is not required to pass through the root.