Largest Binary Search Subtree in Value

Given a binary tree root, return the largest sum of a subtree that is also a binary search tree.

Constraints

• 0 ≤ n ≤ 100,000 where n is the number of nodes in root

https://binarysearch.com/problems/Largest-Binary-Search-Subtree-in-Value

Examples

Example 1

Input

• root =

Output

• answer = 9

Explanation

The binary search tree rooted at 3 has the largest sum with 3 + 2 + 4 = 9

Solution