Python solution with detailed explanation


  • 0
    G

    Solution

    Largest BST Subtree https://leetcode.com/problems/largest-bst-subtree/?tab=Description

    Algorithm

    1. Imagine post-order and visualize the lowest branch.
    2. You need to return the min, max, and a positive number if it is a BST rooted at that node. If not, you send -1. It doesnt matter in that case what min/max you send upwards.
      3.** How does the min and max change if root.left == None or root.right == None. In both cases, we have to replace min/max by root.val. Draw on paper to verify.**
    3. After L & R are completed, test if left and right are valid BST. if yes, then test if root.val is more than maximum in left subtree. Also test if root.val is less than minimum in right subtree.
    4. Base Case Intuition: Imagine a tree which is None. Now the base case tells us that we should return a min value such that for any root.val (say -2), (root.val < min) is true. What is maximum integer value for root.val? Answer: 2^31-1. So the min value must be 2^31. Similarly, the max value should be one less than the minimum integer value or -2^31 such that root.val > max.
    class Solution(object):
        def largestBSTSubtree(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            self.max_so_far = 0
            m1, m2, n = self.helper(root)
            return self.max_so_far
        
        def helper(self, root):
            if root == None:
                return 2**31, -2**31-1, 0  ### IMPORTANT INSIGHT
            min1, max1, n1 = self.helper(root.left)
            min2, max2, n2 = self.helper(root.right)
            if (n1 != -1) and (n2 != -1) and (root.val > max1) and (root.val < min2): ### Important Condition
                self.max_so_far = max(self.max_so_far, n1+n2+1)
                min1 = root.val if root.left == None else min1 ### If root.left is None, then the minimum from subtree is root.val
                max2 = root.val if root.right == None else max2 ### If root.right is None, then the maximum from subtree is root.val
                return min1, max2, n1+n2+1
            else:
                return None, None, -1
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.