Largest Binary Search Subtree in Nodes - Amazon Top Interview Questions

                        Solution in C++ :

tuple<int, int, int, bool> solve(Tree *root, int &mx, Tree *&res) {
    // for null node
    if (!root) return {INT_MAX, INT_MIN, 0, true};

    // fetch answer for the subtrees starting at the left and the right subtree
    auto [leftMin, leftMax, leftRes, leftValid] = solve(root->left, mx, res);
    auto [rightMin, rightMax, rightRes, rightValid] = solve(root->right, mx, res);

    /*
     * check the validity of BST for the subtree at the current node.
     * resHere = 1 + leftRes + rightRes; iff validHere == true;
     * else 0
     */
    int val = root->val;
    bool validHere = leftValid && rightValid && leftMax < val && rightMin > val;
    int resHere = validHere * (1 + leftRes + rightRes);

    // if better answer found update
    if (mx < resHere) {
        mx = resHere;
        res = root;
    }

    return {min({leftMin, rightMin, val}), max({leftMax, rightMax, val}), resHere, validHere};
}

Tree *solve(Tree *root) {
    int mx = 0;
    Tree *res = nullptr;
    solve(root, mx, res);

    return res;
}
                    

                        Solution in Java :

import java.util.*;

/**
 * public class Tree {
 *   int val;
 *   Tree left;
 *   Tree right;
 * }
 */
class Solution {
    Tree ret = null;
    int biggest_size = 0;
    int size = 0;
    public Tree solve(Tree root) {
        recurse(root);
        return ret;
    }
    public void recurse(Tree root) {
        if (root == null)
            return;
        if (is_binary(root) && size > biggest_size) {
            ret = root;
            biggest_size = size;
        }
        size = 0;
        recurse(root.left);
        recurse(root.right);
    }
    public boolean is_binary(Tree root) {
        if (root == null)
            return true;
        if (root.left != null && root.left.val > root.val) {
            return false;
        }
        if (root.right != null && root.right.val < root.val) {
            return false;
        }
        size++;
        return is_binary(root.left) && is_binary(root.right);
    }
}
                    

                        Solution in Python : 
                            
class Solution:
    def solve(self, root):
        numNodes = {}
        # getting the number of Nodes of each subtree
        def dfs(root):
            if not root:
                return 0
            l, r = dfs(root.left), dfs(root.right)
            numNodes[root] = 1 + l + r
            return 1 + l + r

        dfs(root)

        storeMax, retRoot = 0, None
        # validating the BST from bottom to top while tracking the maxNum nodes
        def validate(root, parent):
            nonlocal storeMax, retRoot
            if not root:
                return [True, (parent, parent)]
            resL, minMaxL = validate(root.left, root)
            resR, minMaxR = validate(root.right, root)
            # parent BST ? ==> both left and right are BST and they satisfy the range property
            resRoot = resL and resR and minMaxL[0].val <= root.val <= minMaxR[1].val
            if resRoot:
                if numNodes[root] > storeMax:
                    retRoot, storeMax = root, numNodes[root]
                return [True, (minMaxL[1], minMaxR[0])]
            # current subtree not a BST ==> from this side there will be no contribution towards the result
            return [False, ((None), (None))]

        validate(root, None)
        return retRoot