Compute maximum path sum in a binary tree
Company: TikTok
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
##### Question
You are given the `root` of a binary tree where each node contains an integer value (which may be positive, zero, or negative). Return the **maximum path sum** over all possible paths in the tree.
A **path** is any sequence of nodes such that:
- Each pair of consecutive nodes in the sequence is connected by a parent-child edge in the tree.
- A path may start and end at any nodes in the tree (it is **not** required to pass through the root).
- A path must contain at least one node.
- The path is *simple*: it never reuses a node and never jumps between sibling branches — it always follows child pointers up or down.
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
Assume a typical binary tree node definition, for example in a C++/Java-like style:
```text
class TreeNode {
int val;
TreeNode left;
TreeNode right;
}
```
Write a function:
```text
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.
### Follow-up
Aim for **O(n) time**, where `n` is the number of nodes — a single traversal of the tree.
### Examples
**Example 1**
Input tree (level-order): `[1, 2, 3]`
```text
1
/ \
2 3
```
All simple paths include `2 -> 1 -> 3` (sum 6), `2 -> 1` (sum 3), `1 -> 3` (sum 4), and the single-node paths `2`, `1`, `3`.
Output: `6`
**Example 2**
Input tree (level-order): `[-10, 9, 20, null, null, 15, 7]`
```text
-10
/ \
9 20
/ \
15 7
```
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 may start and end at any two nodes and is **not** required to pass through the root.
- Because node values can be negative, the answer may itself be negative (when every node is negative, the best path is the single largest value).
Quick Answer: TikTok software-engineer technical-screen coding question: given the root of a binary tree with possibly negative node values, return the maximum path sum over any simple path, where a path may start and end at any nodes and need not pass through the root. The intended solution is a single post-order DFS that separates the best path bending through each node (the answer candidate) from the best straight-down branch returned upward, clamping negative child gains at zero and initializing the answer to negative infinity, in O(n) time.
Given a level-order binary tree, return the maximum sum over any non-empty simple path.
Constraints
- level_order uses None for missing nodes
Examples
Input: ([1, 2, 3],)
Expected Output: 6
Explanation: Path 2->1->3.
Input: ([-10, 9, 20, None, None, 15, 7],)
Expected Output: 42
Explanation: Path 15->20->7.
Input: ([-3],)
Expected Output: -3
Explanation: Single negative node.
Input: ([2, -1],)
Expected Output: 2
Explanation: Best may ignore a negative child.
Hints
- At each node, update a global best using the best nonnegative gain from each side.