Java sol with explanation having O(n) runtime


  • 0
    C

    This approach takes some idea from the solution of Validate if BST problem.

        public int largestBSTSubtree(TreeNode root) {
            int[] result = findSubtree(root);
            return result == null ? 0 : result[0];    
        }
        
        private int[] findSubtree(TreeNode node) {
            // Base case
    		if (node == null) {
    			return null;
    		}
    
    		int[] leftChild = findSubtree(node.left);
    		int[] rightChild = findSubtree(node.right);
    
    		int leftChildVal = node.left == null ? Integer.MIN_VALUE : node.left.val;
    		int rightChildVal = node.right == null ? Integer.MAX_VALUE : node.right.val;
        
            // initializing the min left and max right of subtree for the current node same as root
            int leftMin = node.val, rightMax = node.val;
            
            // initializing the left subtree node and right subtree nodes for the currrent node as 0 
            int leftNodes = 0, rightNodes = 0;
    
            // checking immidiate child nodes
    		boolean isBinaryNode = leftChildVal <= node.val && rightChildVal > node.val;
    		
    		
    		if(leftChild != null){
    		    // checking if max right of left node is less than current node and left node has a BST subtree
    		    isBinaryNode = isBinaryNode && leftChild[2] < node.val && leftChild[3] == 1;
    		    // assigning acutal left min for the current node
    		    leftMin = leftChild[1];
    		    // assigning acutal node count of left subtree 
    		    leftNodes = leftChild[0];
    		}
    		
    		if(rightChild != null){
    		    // checking if min left of right node is greater than current node and right node has a BST subtree
    		    isBinaryNode = isBinaryNode && rightChild[1] > node.val && rightChild[3] == 1;
    		    // assigning acutal right max for the current node
    		    rightMax = rightChild[2];
    		    // assigning acutal node count of right subtree 
    		    rightNodes = rightChild[0];
    		}
    		
    		if (isBinaryNode) {
    			return new int[] { leftNodes + rightNodes + 1, leftMin, rightMax, 1 };
    		}
    
            // if no longer BST is followed
    		return new int[] { Math.max(leftNodes, rightNodes), leftMin, rightMax, 0 };
    	}
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.