/333. Largest BST Subtree
Previous|Next

333. Largest BST Subtree

Medium
Dynamic Programming45.8% acceptance

Given the root node of a binary tree, determine the size (number of nodes) of the largest subtree that is a binary search tree (BST). A BST is defined as a binary tree in which for every node, all nodes in its left subtree have values less than the nodes value, and all nodes in its right subtree have values greater than the nodes value.

Example 1

Input: TreeNode(10, TreeNode(5, TreeNode(1), TreeNode(8)), TreeNode(15, None, TreeNode(7)))

Output: 3

Explanation: The largest BST subtree is rooted at node 5 with nodes 5, 1, 8.

Example 2

Input: TreeNode(2, TreeNode(1), TreeNode(3))

Output: 3

Explanation: The whole tree is a BST.

Constraints

  • 1 <= number of nodes in the tree <= 10^4
  • -10^5 <= node value <= 10^5
Python (current runtime)

Case 1

Input: TreeNode(6, TreeNode(1), TreeNode(10, TreeNode(8, TreeNode(7), TreeNode(9)), TreeNode(15, TreeNode(13), TreeNode(17))))

Expected: 7

Case 2

Input: TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode(6, TreeNode(5), TreeNode(7)))

Expected: 7

Case 3

Input: TreeNode(5, TreeNode(4), TreeNode(6, None, TreeNode(3)))

Expected: 2