Leetcode 333. Largest BST Subtree

Problem Explanation

Given a binary tree, we need to find the biggest subtree which is also a binary search tree. A binary search tree (BST) is a tree in which for each node, the values of all the nodes in its left subtree are less than or equal than the node´s value, and the values of all nodes in its right subtree are greather than the node's value. In this problem, the largest subtree is the one with the most number of nodes. Therefore, we want to find the BST within our input tree that contains the most elements. There are no restrictions for these numbers being consecutive or not, and also no restrictions as to where can the desired BST be.

Consider the example below:

1
2
3     10
4    /   \
5   5    15
6  / \     \
71    8    7
8

In this case, the largest BST is the one highlighted, having the values 5, 1 and 8 and size 3. Even though the 15 has 7 as its children, the condition for the right subtree being greater than the node's value is not fulfilled, therefore it is not a BST.

Approach Explanation

Firstly, we will consider every node of the tree and its children recursively through a simple depth-first-search. For each node, we will check the conditions to be a BST. This will involve comparing the node's value to the maximum value in its left subtree and the minimum value in the right subtree, and if the node's value is greater than its maximum left child and less than its minimum right child, we consider this sub-tree as a BST. If any of these conditions is not satisfied, the sub-tree cannot be a BST. In those cases, we will return the maximum size between the left and right sub-tree. Therefore, we will keep checking from down to up, at each step deciding if the subtree under consideration is a BST, and keep the value of the maximum size seen so far. We essentially perform a bottom-up inspection and the complexity remains O(n), because each node is only visited once.

Python Solution

1
2python
3class TreeNode:
4    def __init__(self, x):
5        self.val = x
6        self. left = None
7        self.right = None
8      
9class Solution:
10    def largestBSTSubtree(self, root: TreeNode) -> int:
11        def dfs(node):
12            if not node: return [0, float('inf'), float('-inf')]
13            l, min1, max1 = dfs(node.left) # using post order traversal
14            r, min2, max2 = dfs(node.right)
15            if max1 < node.val < min2:
16                return l + r + 1, min(min1, node.val), max(max2, node.val)
17            else:
18                return max(l, r), float('-inf'), float('inf')
19
20        return dfs(root)[0]

Java Solution

1
2java
3public class TreeNode {
4        int val;
5        TreeNode left;
6        TreeNode right;
7        TreeNode(int x) { val = x; }
8}
9
10public class Solution {
11public int largestBSTSubtree(TreeNode root) {
12    int[] res = dfs(root);
13    return res[1];
14}
15
16public int[] dfs(TreeNode root) {
17    if (root == null)
18        return new int[]{0, 0, Integer.MAX_VALUE, Integer.MIN_VALUE};
19    int[] left = dfs(root.left);
20    int[] right = dfs(root.right);
21    if (left[0] == -1 || right[0] == -1 || root.val <= left[3] || root.val >= right[2])
22        return new int[]{-1, 0, 0, 0};
23    return new int[]{1, left[1] + right[1] + 1, Math.min(left[2], root.val), Math.max(right[3], root.val)};
24}
25}

C++ Solution

1
2C++
3struct TreeNode {
4    int val;
5    TreeNode *left;
6    TreeNode *right;
7    TreeNode(int x): val(x), left(NULL), right(NULL) {}
8  };
9
10class Solution {
11public:
12
13    struct Subtree {
14        int size;
15        bool is_bst;
16        int min_val;
17        int max_val;
18        int max_size;
19
20        Subtree(): size(0), is_bst(true), min_val(INT_MAX), max_val(INT_MIN), max_size(0) {}
21    };
22
23    int largestBSTSubtree(TreeNode* root) {
24        return dfs(root).max_size;
25    }
26     
27    Subtree dfs(TreeNode* root) {
28        Subtree cur;
29        if(!root)
30            return cur;
31        Subtree l = dfs(root->left);
32        Subtree r = dfs(root->right);
33        if (!l.is_bst || !r.is_bst || root->val <= l.max_val || root->val >= r.min_val)
34            cur.is_bst = false;
35        else {
36            cur.size = l.size + r.size + 1;
37            cur.is_bst = true;
38            cur.min_val = root->left ? l.min_val : root->val;
39            cur.max_val = root->right ? r.max_val : root->val;
40            cur.max_size = cur.size;
41            cur.max_size = max(cur.max_size, max(l.max_size, r.max_size));
42        }
43        return cur;
44    }
45};

C# Solution

1
2Csharp
3public class Solution {
4    int res = 0;
5    public int LargestBSTSubtree(TreeNode root) {
6        if (root == null) return 0;
7        Helper(root);
8        return res;
9    }
10    private int[] Helper(TreeNode node){
11        if (node == null) return new int[4] {0, 1, Int32.MaxValue, Int32.MinValue};
12        int[] left = Helper(node.left), right = Helper(node.right);
13        int[] b = new int[4] { -1, -1, -1, -1}; 
14        if (left[1] == 1 && right[1] == 1 && left[2] < node.val && node.val < right[3]){
15            b[0] = left[0] + right[0] + 1; 
16            res = Math.Max(res, b[0]); 
17            b[1] = 1; 
18            b[2] = Math.Min(left[2], node.val); 
19            b[3] = Math.Max(right[3], node.val); 
20        }
21        else b[1] = -1;
22        return b;
23    }
24    
25    public class TreeNode {
26      public int val;
27      public TreeNode left;
28      public TreeNode right;
29     }
30}

Javascript Solution

1
2javascript
3class TreeNode {
4    constructor(val, left = null, right = null) {
5        this.val = val;
6        this.left = left;
7        this.right = right;
8    }
9}
10
11class NodeRes {
12    constructor(size, min, max) {
13        this.size = size;
14        this.min = min;
15        this.max = max;
16        this.largestBstSize = size;
17    }
18}
19
20class Solution {
21    largestBSTSubtree(root) {
22        return this.traverse(root).largestBstSize;
23    }
24    
25    traverse(root) {
26        if (root === null) return new NodeRes(0, Infinity, -Infinity);
27        let left = this.traverse(root.left);
28        let right = this.traverse(root.right);
29        if (root.val > left.max && root.val < right.min) {
30            let size = 1 + left.size + right.size;
31            return new NodeRes(size, Math.min(root.val, left.min), Math.max(root.val, right.max), size);
32        } else {
33            return new NodeRes(0, -Infinity, Infinity, Math.max(left.largestBstSize, right.largestBstSize));
34        }
35    }
36}

In the solutions provided, you can notice that each function has its unique approach to solving the problem.

In the Python solution, the function largestBSTSubtree traverses the tree depth-first (from bottom-up) and checks whether each node is a BST or not. It makes use of helper function dfs to perform these checks and computes the number of nodes. This solution is proficient because it only iterates over all nodes once, making it a very efficient O(n) solution.

The Java solution works almost similarly to the Python solution. It has a helper function dfs, which checks if each node is a BST by comparing it with the maximum value from the left sub-tree and minimum value from the right sub-tree. The result is kept track using a variable res.

The C++ solution creates a structure called Subtree. This structure stores the size of the current largest BST, the maximum and minimum values of the node, whether the current subtree is a BST or not, and the maximum size of the subtree.

The C# solution is similar to the other solutions where it makes use of a helper function. It also maintains a variable res that stores the maximum subtree size found so far. It then performs a comparison of node.val with immediate left and right child node values. If the current subtree is a BST, it updates b[3] and b[2] to keep track of the current maximum and minimum values checkings if the tree is BST-valid, and updating the largest BST.

In the Javascript solution, the largestBSTSubtree function makes use of a helper function traverse. This function retreives the minimum and maximum subtrees and checks the subtree from that specific node, and if it's valid it updates the current BST size. If it's not, it keeps the largest seen so far. This solution, like the Python, Java, C# and C++ solutions, only traverses all the nodes once, giving it a time complexity of O(n).

These solutions work for any binary trees, even those with negative values and those that are not balanced. Overall, these solutions have a time complexity of O(n), where n is the number of nodes in the tree, since each node is only processes once.

These approaches are very optimal, considering the worst case scenario, the total time complexity remains O(n) for each of the provided solutions.