Quick Overview

Coding problem: given a binary tree in level-order form whose node values may be negative, find the largest sum of any path of connected nodes, where the path may start and end anywhere in the tree. It tests tree recursion, combining results from both subtrees, and correct handling of all-negative values.

Largest path sum in a binary tree with negative node values

Company: ByteDance

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

A binary tree stores an integer, possibly negative, in each node. A path is a sequence of one or more distinct nodes in which every two consecutive nodes are joined by an edge between a parent and its child. A path does not need to pass through the root, and it can start and end at any nodes, including the same node. Return the largest possible sum of the node values on a path. ### Function Signature ```python def max_path_sum(values: list[int | None]) -> int: ``` `values` describes the tree in level order, as defined under Rules. ### Rules - Tree encoding: `values[0]` is the root. The remaining entries give children in pairs, left child then right child, for each non-null node in the order those nodes appear in `values`. `None` marks a missing child, and the children of a missing node are not listed. Trailing `None` entries may be omitted. - The sum of a path is the sum of the values of its nodes. Each node appears at most once on a path, so a path can rise from one node to a common ancestor and descend to another node, but it cannot turn back. - A path contains at least one node, so the answer is defined even when every value is negative. ### Constraints - The tree has between 1 and `3 * 10^4` nodes, and `values[0]` is not `None`. - `-1000 <= node value <= 1000` - The absolute value of the answer is at most `3 * 10^7`. ### Examples **Example 1** ```text Input: values = [2, -1, 3] Output: 5 ``` The path from the root to its right child gives 2 + 3 = 5. Extending it to the left child -1 would lower the sum to 4. **Example 2** ```text Input: values = [-5, 4, 8, None, None, 6, -2, 1] Output: 15 ``` The root -5 has children 4 and 8; node 4 has no children; node 8 has children 6 and -2; node 6 has the left child 1. The best path is 1, 6, 8, with sum 15. It does not include the root: extending it through -5 to 4 would give 14. **Example 3** ```text Input: values = [-3, -1, -2] Output: -1 ``` Every value is negative, so the best path is the single node -1.

Overview: Coding problem: given a binary tree in level-order form whose node values may be negative, find the largest sum of any path of connected nodes, where the path may start and end anywhere in the tree. It tests tree recursion, combining results from both subtrees, and correct handling of all-negative values.

A binary tree stores an integer, possibly negative, in each node. A path is a sequence of one or more distinct nodes in which every two consecutive nodes are joined by an edge between a parent and its child. A path does not need to pass through the root, and it can start and end at any nodes, including the same node. The sum of a path is the sum of the values of its nodes. Each node appears at most once on a path, so a path can rise from one node to a common ancestor and descend to another node, but it cannot turn back. Implement `max_path_sum(values)`, which returns the largest possible sum of the node values on a path. A path contains at least one node, so the answer is defined even when every value is negative. **Tree encoding.** `values` describes the tree in level order. `values[0]` is the root. The remaining entries give children in pairs, left child then right child, for each non-null node in the order those nodes appear in `values`. `None` marks a missing child, and the children of a missing node are not listed. Trailing `None` entries may be omitted. (A missing child is `null` in JavaScript and Java, and an empty `std::optional` in C++.) **Constraints** - The tree has between 1 and 3 * 10^4 nodes, and `values[0]` is not `None`. - -1000 <= node value <= 1000 - The absolute value of the answer is at most 3 * 10^7, so every path sum fits in a 32-bit signed integer (`int` in Java and C++). **Example 1** Input: values = [2, -1, 3] Output: 5 The path from the root to its right child gives 2 + 3 = 5. Extending it to the left child -1 would lower the sum to 4. **Example 2** Input: values = [-5, 4, 8, None, None, 6, -2, 1] Output: 15 The root -5 has children 4 and 8; node 4 has no children; node 8 has children 6 and -2; node 6 has the left child 1. The best path is 1, 6, 8, with sum 15. It does not include the root: extending it through -5 to 4 would give 14.

Constraints

  • The tree has between 1 and 3 * 10^4 nodes, and values[0] is not None.
  • -1000 <= node value <= 1000
  • The absolute value of the answer is at most 3 * 10^7 (it fits in a 32-bit signed integer).
  • values is a valid level-order encoding: children are listed in pairs (left, then right) for each non-null node in the order those nodes appear, None marks a missing child, children of missing nodes are not listed, and trailing None entries may be omitted.

Examples

Input: ([2, -1, 3],)

Expected Output: 5

Explanation: Source Example 1: root plus right child gives 2 + 3 = 5; adding the left child -1 would lower it to 4.

Input: ([-5, 4, 8, None, None, 6, -2, 1],)

Expected Output: 15

Explanation: Source Example 2: best path 1, 6, 8 lies in a subtree and excludes the root; None children mid-level and an omitted trailing None.

Hints

  1. Every path has exactly one node that is closest to the root. The path can rise to that node from one side and descend from it on the other side, but it never turns back.
  2. A path must contain at least one node, so the answer can be negative. Do not let an empty path count as 0.
  3. Before computing anything, rebuild the parent-child links. Children are listed in pairs only for nodes that are not None, in the order those nodes appear.

Loading coding console...

Show the approach

Approach

Rebuild the tree from the level-order encoding. Keep a pointer p to the next non-null node whose children have not been read yet, and consume the remaining entries two at a time as that node's left and right child; every non-null entry becomes a new node with the next index. Nodes are numbered in level order, so every child has a larger index than its parent, and scanning the indices from last to first visits each node after both of its children. No recursion is needed, which matters because a chain can be 3 * 10^4 nodes deep.

For each node k let down[k] be the largest sum of a path that starts at k and goes downward through at most one child: down[k] = value[k] + max(0, down[left], down[right]), where a missing child contributes 0. Every path has exactly one topmost node t (the node closest to the root). The path is t plus an optional downward path into the left subtree and an optional downward path into the right subtree. Those two parts are independent because the subtrees are disjoint, so the best path whose topmost node is t has sum value[t] + max(0, down[left]) + max(0, down[right]). The answer is the maximum of this quantity over all nodes, and every candidate is the sum of a real path, so the maximum is exact.

Edge cases: a single-node tree returns its own value. When every value is negative, both branches are clamped to 0 and the answer is the largest single value; the running best starts from a real node value, never from 0. Explicit and omitted trailing None entries parse identically. Every path sum is bounded by 3 * 10^7 in absolute value, so 32-bit integers suffice.

Time complexity:
O(n)
Space complexity:
O(n)