Largest BST Subtree

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.

public int largestBSTSubtree(TreeNode root) {

    helper(root);

    return maxSubTree;
}

private int maxSubTree = 0;

private SubTreeInfo helper(TreeNode root){

    if(root == null) return null;

    SubTreeInfo leftTreeInfo = helper(root.left), 
                rightTreeInfo = helper(root.right);

    SubTreeInfo currNodeInfo = new SubTreeInfo(root.val, root.val);
    boolean isBST = true;

    if(leftTreeInfo != null){
        if(leftTreeInfo.max < root.val && leftTreeInfo.count != -1){
            currNodeInfo.min = leftTreeInfo.min;
            currNodeInfo.count += leftTreeInfo.count;
        }else isBST = false;
    }

    if(rightTreeInfo != null){
        if(rightTreeInfo.min > root.val && rightTreeInfo.count != -1){
            currNodeInfo.max = rightTreeInfo.max;
            currNodeInfo.count += rightTreeInfo.count;
        }else isBST = false;
    }

    if(!isBST){
        currNodeInfo.count = -1;
    }else maxSubTree = Math.max(maxSubTree, currNodeInfo.count);

    return currNodeInfo;
}


class SubTreeInfo{

    int count = 1;
    int max;
    int min;

    SubTreeInfo(int max, int min){
        this.max = max;
        this.min = min;
    }
}

results matching ""

    No results matching ""