InternDoor

The richest path through a tree

Hardtrees · depth-first search · dynamic programming

Reported in interviews at (where)

A path in a binary tree is a run of nodes in which each node is joined to the next by an edge, and no node is used twice. It has at least one node, and it need not pass through the root. Its sum is the total of its nodes' values.

Return the largest sum of any path in the tree.

Example 1
Input
root = [2,-6,8,null,null,-1,5]
Output
15

The path 5, 8, 2 adds up to 15. Going on to -6 or -1 would only lower it.

Example 2
Input
root = [-4,-7,-2]
Output
-2

Every value is negative, so the best path is the single largest node.

Limits

  • 1 <= number of nodes <= 20000
  • -1000 <= Node.val <= 1000
  • the tree is at most 3000 levels deep

Hints

Hint 1

For each node, work out the best sum of a path that starts at it and goes down one side. A side worth less than 0 is better left out.

Hint 2

The best path that bends at a node is its value plus the best way down on each side. Track the largest of those as you go.

Where this was reported

Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.

Run your code to check it on the examples. Submit runs every hidden test.

Ready for the real one?

Engineering internships and entry-level jobs in India, newest first.