Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/333.html

Level

Medium

Description

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.

Note:

A subtree must include all of its descendants.

Example:

Input: [10,5,15,1,8,null,7]

   10 
   / \ 
  5  15 
 / \   \ 
1   8   7

Output: 3
Explanation: The Largest BST Subtree in this case is the subtree [5,1,8]. The return value is the subtree's size, which is 3.

Follow up:

Can you figure out ways to solve it with O(n) time complexity?

Algorithm

For each node, verify whether it is BST, and if it is, count the number of nodes.

Code

  • 
    public class Largest_BST_Subtree {
        /**
         * Definition for a binary tree node.
         * public class TreeNode {
         *     int val;
         *     TreeNode left;
         *     TreeNode right;
         *     TreeNode(int x) { val = x; }
         * }
         */
    
        public class Solution {
    
            private int max = 0;
    
            public int largestBSTSubtree(TreeNode root) {
                if (root == null) {
                    return 0;
                }
    
                dfs(root);
    
                return max;
            }
    
            private SubTreeData dfs(TreeNode root) {
                SubTreeData curr = new SubTreeData();
                if (root == null) {
                    curr.isBST = true;
                    return curr;
                }
    
                SubTreeData left = dfs(root.left);
                SubTreeData right = dfs(root.right);
    
                curr.lower = Math.min(root.val, Math.min(left.lower, right.lower));
                curr.upper = Math.max(root.val, Math.max(left.upper, right.upper));
    
                if (left.isBST && root.val > left.upper && right.isBST && root.val < right.lower) {
                    curr.size = left.size + right.size + 1;
                    curr.isBST = true;
                    max = Math.max(max, curr.size);
                } else {
                    curr.size = 0; // can delete, already is 0. just like isBST already false
                }
    
                return curr;
            }
        }
    
        class SubTreeData {
            int size = 0; // exclude root self
            int lower = Integer.MAX_VALUE;
            int upper = Integer.MIN_VALUE;
            boolean isBST = false;
        }
    }
    
    ############
    
    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode() {}
     *     TreeNode(int val) { this.val = val; }
     *     TreeNode(int val, TreeNode left, TreeNode right) {
     *         this.val = val;
     *         this.left = left;
     *         this.right = right;
     *     }
     * }
     */
    class Solution {
        private int ans;
    
        public int largestBSTSubtree(TreeNode root) {
            ans = 0;
            dfs(root);
            return ans;
        }
    
        private int[] dfs(TreeNode root) {
            if (root == null) {
                return new int[] {Integer.MAX_VALUE, Integer.MIN_VALUE, 0};
            }
            int[] left = dfs(root.left);
            int[] right = dfs(root.right);
            if (left[1] < root.val && root.val < right[0]) {
                ans = Math.max(ans, left[2] + right[2] + 1);
                return new int[] {
                    Math.min(root.val, left[0]), Math.max(root.val, right[1]), left[2] + right[2] + 1};
            }
            return new int[] {Integer.MIN_VALUE, Integer.MAX_VALUE, 0};
        }
    }
    
  • // OJ: https://leetcode.com/problems/largest-bst-subtree/
    // Time: O(N)
    // Space: O(H)
    class Solution {
        int ans = 0;
        array<int, 3> dfs(TreeNode *root) { // min, max, count. If invalid, count = -1
            if (!root) return {INT_MAX,INT_MIN,0};
            auto left = dfs(root->left), right = dfs(root->right);
            bool valid = left[2] != -1 && right[2] != -1 && left[1] < root->val && right[0] > root->val;
            if (valid) ans = max(ans, 1 + left[2] + right[2]);
            return {left[2] ? left[0] : root->val, right[2] ? right[1] : root->val, valid ? 1 + left[2] + right[2] : -1};
        }
    public:
        int largestBSTSubtree(TreeNode* root) {
            dfs(root);
            return ans;
        }
    };
    
  • '''
    >>> float("inf")
    inf
    >>> float("inf") + 1
    inf
    >>> import math
    >>> float("inf") == math.inf
    True
    '''
    # Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, val=0, left=None, right=None):
    #         self.val = val
    #         self.left = left
    #         self.right = right
    class Solution:
        def largestBSTSubtree(self, root: Optional[TreeNode]) -> int:
            def dfs(root):
                if root is None:
                    return inf, -inf, 0
                lmi, lmx, ln = dfs(root.left)
                rmi, rmx, rn = dfs(root.right)
                nonlocal ans
                # this if can check if left/right is a bst
                # eg. if left is not bst, the returned lmi=-inf and lmx=inf, so 'lmx < root.val < rmi' is false
                if lmx < root.val < rmi:
                    ans = max(ans, ln + rn + 1)
                    # lmi is guranteed < root.val, except when left(right) is None
                    return min(lmi, root.val), max(rmx, root.val), ln + rn + 1
                return -inf, inf, 0 # if this one not bst, then all parents will not be bst
    
            ans = 0
            dfs(root)
            return ans
    
    ############
    
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
      def largestBSTSubtree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
    
        def helper(root):
          if not root:
            return (0, 0, float("inf"), float("-inf"))  # numBST, maxNumBST, min, max
          lnumBST, lmaxNumBST, lmin, lmax = helper(root.left)
          rnumBST, rmaxNumBST, rmin, rmax = helper(root.right)
          numBST = -1
          if lmax < root.val < rmin and lnumBST != -1 and rnumBST != -1:
            numBST = 1 + lnumBST + rnumBST
          maxNumBST = max(1, lmaxNumBST, rmaxNumBST, numBST)
          return numBST, maxNumBST, min(lmin, rmin, root.val), max(lmax, rmax, root.val)
    
        return helper(root)[1]
    
    
  • /**
     * Definition for a binary tree node.
     * type TreeNode struct {
     *     Val int
     *     Left *TreeNode
     *     Right *TreeNode
     * }
     */
    func largestBSTSubtree(root *TreeNode) int {
    	ans := 0
    	var dfs func(root *TreeNode) []int
    	dfs = func(root *TreeNode) []int {
    		if root == nil {
    			return []int{math.MaxInt32, math.MinInt32, 0}
    		}
    		left := dfs(root.Left)
    		right := dfs(root.Right)
    		if left[1] < root.Val && root.Val < right[0] {
    			ans = max(ans, left[2]+right[2]+1)
    			return []int{min(root.Val, left[0]), max(root.Val, right[1]), left[2] + right[2] + 1}
    		}
    		return []int{math.MinInt32, math.MaxInt32, 0}
    	}
    	dfs(root)
    	return ans
    }
    
    func max(a, b int) int {
    	if a > b {
    		return a
    	}
    	return b
    }
    
    func min(a, b int) int {
    	if a < b {
    		return a
    	}
    	return b
    }
    

All Problems

All Solutions