Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

333. Largest BST Subtree

Time: $O(n)$

Space: $O(n)$

			


struct T {
  int min;   // Min value in the subtree
  int max;   // Max value in the subtree
  int size;  // Total size of the subtree
};

class Solution {
 public:
  int largestBSTSubtree(TreeNode* root) {
    return dfs(root).size;
  }

 private:
  T dfs(TreeNode* root) {
    if (root == nullptr)
      return {INT_MAX, INT_MIN, 0};

    T l = dfs(root->left);
    T r = dfs(root->right);

    if (l.max < root->val && root->val < r.min)
      return {min(l.min, root->val), max(r.max, root->val),
              1 + l.size + r.size};

    // Mark as invalid one, but still record the size of children
    // Returns (-INF, INF) because any node won't > INT and < -INF
    return {INT_MIN, INT_MAX, max(l.size, r.size)};
  }
};




			


class T {
  public int min;  // Min value in the subtree
  public int max;  // Max value in the subtree
  public int size; // Total size of the subtree

  public T(int min, int max, int size) {
    this.min = min;
    this.max = max;
    this.size = size;
  }
}

class Solution {
  public int largestBSTSubtree(TreeNode root) {
    return dfs(root).size;
  }

  private T dfs(TreeNode root) {
    if (root == null)
      return new T(Integer.MAX_VALUE, Integer.MIN_VALUE, 0);

    T l = dfs(root.left);
    T r = dfs(root.right);

    if (l.max < root.val && root.val < r.min)
      return new T(Math.min(l.min, root.val), Math.max(r.max, root.val), 1 + l.size + r.size);

    // Mark as invalid one, but still record the size of children
    // Returns (-INF, INF) because any node won't > INT and < -INF
    return new T(Integer.MIN_VALUE, Integer.MAX_VALUE, Math.max(l.size, r.size));
  }
}