Maximum path sum in a binary tree
Coding problemHardAsked in: Flipkart, Google, Meta, NPCI
A path in a binary tree is a sequence of nodes where each pair of neighbours is joined by an edge, and no node appears twice. A path has at least one node and does not have to pass through the root.
Given the root of a non-empty binary tree, return the largest sum of values along any path. Values can be negative. Trees are written in level order, with null for a missing child.
Examples
Example 1
Input: root = [1,2,3]
Output: 6
The path 2, 1, 3.
Example 2
Input: root = [-10,9,20,null,null,15,7]
Output: 42
The path 15, 20, 7.
Example 3
Input: root = [-3]
Output: -3
Constraints
- The tree has between 1 and 100,000 nodes
- Each value is between -1,000 and 1,000
Run checks the 3 examples. Submit also runs the hidden tests: edge cases, large inputs and a time limit.
Run your code to see the results here. Ctrl or Cmd + Enter runs; add Shift to submit.