largest_bst_subtree
1from typing import Optional 2from utils import TreeNode 3 4 5# @leet start 6# Definition for a binary tree node. 7class NodeValue: 8 def __init__(self, min_node, max_node, max_size): 9 self.max_node = max_node 10 self.min_node = min_node 11 self.max_size = max_size 12 13 14class Solution: 15 """ 16 This question asks us to find the largest subtree which is also a Binary 17 Search Tree. We can do this by enforcing the invariant that each subtree 18 is a BST. This can be done in $O(n^2)$ time, by checking for each node, 19 if it is a valid BST. We can figure out if a tree is a BST by checking its 20 properties, that its left side is less than root.val and its right side 21 is greater than root.val for every item in the tree. 22 23 We can optimize this by bubbling up the information all the way to the parent. 24 This is done by making it so each tree returns 3 points of information: 25 26 Its allowed maximum val, its allowed minimum val, and its maximum size. 27 We then need to handle each case: 28 29 If the node itself is None, it has a size of 0 but it can be any valid BST. 30 So we return float('inf') for max, float('-inf') for min, and 0 for size. 31 32 Otherwise, we check the left and right subtrees. If the left and right subtrees 33 follow the property of left.max < node.val < right.min, then we have a valid 34 BST at our current node. We can set our current max to min(node.val, left.min) 35 and our min to max(node.val, right.max) and then return left.size + right.size 36 + 1 for our size. 37 38 Otherwise, we need to return that this tree is not a BST, thus we would return 39 up the maximum size of the left or right subtree, and then return an invalid 40 configuration, where the maximum is the minimum allowed number, and the minimum 41 is the maximum allowed number. 42 """ 43 44 def traverse(self, node): 45 if not node: 46 return NodeValue(float("inf"), float("-inf"), 0) 47 48 left = self.traverse(node.left) 49 right = self.traverse(node.right) 50 51 if left.max_node < node.val < right.min_node: 52 return NodeValue( 53 min(node.val, left.min_node), 54 max(node.val, right.max_node), 55 left.max_size + right.max_size + 1, 56 ) 57 58 return NodeValue( 59 float("-inf"), float("inf"), max(left.max_size, right.max_size) 60 ) 61 62 def largestBSTSubtree(self, node: Optional[TreeNode]) -> int: 63 return self.traverse(node).max_size 64 65 66# @leet end 67 68 69def test(): 70 assert 2 + 2 == 4
8class NodeValue: 9 def __init__(self, min_node, max_node, max_size): 10 self.max_node = max_node 11 self.min_node = min_node 12 self.max_size = max_size
15class Solution: 16 """ 17 This question asks us to find the largest subtree which is also a Binary 18 Search Tree. We can do this by enforcing the invariant that each subtree 19 is a BST. This can be done in $O(n^2)$ time, by checking for each node, 20 if it is a valid BST. We can figure out if a tree is a BST by checking its 21 properties, that its left side is less than root.val and its right side 22 is greater than root.val for every item in the tree. 23 24 We can optimize this by bubbling up the information all the way to the parent. 25 This is done by making it so each tree returns 3 points of information: 26 27 Its allowed maximum val, its allowed minimum val, and its maximum size. 28 We then need to handle each case: 29 30 If the node itself is None, it has a size of 0 but it can be any valid BST. 31 So we return float('inf') for max, float('-inf') for min, and 0 for size. 32 33 Otherwise, we check the left and right subtrees. If the left and right subtrees 34 follow the property of left.max < node.val < right.min, then we have a valid 35 BST at our current node. We can set our current max to min(node.val, left.min) 36 and our min to max(node.val, right.max) and then return left.size + right.size 37 + 1 for our size. 38 39 Otherwise, we need to return that this tree is not a BST, thus we would return 40 up the maximum size of the left or right subtree, and then return an invalid 41 configuration, where the maximum is the minimum allowed number, and the minimum 42 is the maximum allowed number. 43 """ 44 45 def traverse(self, node): 46 if not node: 47 return NodeValue(float("inf"), float("-inf"), 0) 48 49 left = self.traverse(node.left) 50 right = self.traverse(node.right) 51 52 if left.max_node < node.val < right.min_node: 53 return NodeValue( 54 min(node.val, left.min_node), 55 max(node.val, right.max_node), 56 left.max_size + right.max_size + 1, 57 ) 58 59 return NodeValue( 60 float("-inf"), float("inf"), max(left.max_size, right.max_size) 61 ) 62 63 def largestBSTSubtree(self, node: Optional[TreeNode]) -> int: 64 return self.traverse(node).max_size
This question asks us to find the largest subtree which is also a Binary Search Tree. We can do this by enforcing the invariant that each subtree is a BST. This can be done in $O(n^2)$ time, by checking for each node, if it is a valid BST. We can figure out if a tree is a BST by checking its properties, that its left side is less than root.val and its right side is greater than root.val for every item in the tree.
We can optimize this by bubbling up the information all the way to the parent. This is done by making it so each tree returns 3 points of information:
Its allowed maximum val, its allowed minimum val, and its maximum size. We then need to handle each case:
If the node itself is None, it has a size of 0 but it can be any valid BST. So we return float('inf') for max, float('-inf') for min, and 0 for size.
Otherwise, we check the left and right subtrees. If the left and right subtrees follow the property of left.max < node.val < right.min, then we have a valid BST at our current node. We can set our current max to min(node.val, left.min) and our min to max(node.val, right.max) and then return left.size + right.size
- 1 for our size.
Otherwise, we need to return that this tree is not a BST, thus we would return up the maximum size of the left or right subtree, and then return an invalid configuration, where the maximum is the minimum allowed number, and the minimum is the maximum allowed number.
45 def traverse(self, node): 46 if not node: 47 return NodeValue(float("inf"), float("-inf"), 0) 48 49 left = self.traverse(node.left) 50 right = self.traverse(node.right) 51 52 if left.max_node < node.val < right.min_node: 53 return NodeValue( 54 min(node.val, left.min_node), 55 max(node.val, right.max_node), 56 left.max_size + right.max_size + 1, 57 ) 58 59 return NodeValue( 60 float("-inf"), float("inf"), max(left.max_size, right.max_size) 61 )