FunctionRacerProblemsRace

Richest Search Tree Inside

HardTreesPython, JavaScript, TypeScript, Java, C++

You are given the root of a binary tree. A subtree is a node together with everything below it.

A subtree is a search tree when, for each of its nodes, all values in the left part are smaller than the node and all values in the right part are larger. Equal values are not allowed on either side.

Return the largest sum of values of a subtree that is a search tree. If every such subtree has a negative sum, return 0.

Trees appear in the tests in level order, with null for a missing child, like [3,9,20,null,null,15,7]. Each node is a TreeNode with .val, .left and .right; the class is already defined for you.

Example 1

root [10,5,15,1,8,null,7]
returns 14

Under 15 the value 7 sits on the wrong side, so neither that subtree nor the whole tree counts. The subtree at 5 is a search tree with sum 1 + 5 + 8 = 14.

Example 2

root [4,2,9,1,3,8,10]
returns 37

The whole tree is a search tree.

Example 3

root [-4,-2,-5]
returns 0

The leaves are search trees, but their sums are below 0.

Constraints

Race itor take your time

Write it in your browser, against the clock. The model solution, stepped through line by line, comes after.

More Trees problems