Biggest Search Subtree

Medium

You get the root of a binary tree. A subtree is a node together with *all* of its descendants; branches cannot be cut off. A subtree is a search tree if, for each of its nodes, every value in the left branch is strictly smaller than the node's value and every value in the right branch is strictly larger. Return the number of nodes in the biggest subtree that is a search tree. For an empty tree the answer is 0. Try to do it in O(n).

Example 1

root=tree_node([12, 6, 20, 2, 9, 15, 11]) → 3

The whole tree fails because 11 sits to the right of 12. The branch rooted at 6 (nodes 2, 6, 9) is a search tree of 3 nodes; the branch at 20 fails since its right child 11 is smaller than 20.

Example 2

root=tree_node([5, 5]) → 1

Equal values break the rule, so only the leaf 5 qualifies: one node.

Example 3

root=tree_node([]) → 0

The tree is empty, so the answer is 0.

Constraints

The tree has between 0 and 10⁵ nodes
-10⁴ ≤ Node.val ≤ 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Tree Depth-First Search Binary Search Tree Dynamic Programming Binary Tree

Similar problems

Heaviest Search Subtree Hard Counting Search Tree Shapes Medium Is It a Search Tree? Medium Two Mixed-Up Nodes Medium K-th Smallest in a Search Tree Medium

Input

root=tree_node([12, 6, 20, 2, 9, 15, 11])

Expected

Run checks the first 3 tests in your browser. Submit checks all 123 tests on the server, hidden ones included.