Find the size of largest bst in a binary tree

Given a binary tree which contain n nodes. Our goal is to find maximum size subtree which is form of BST in binary tree.

Find size of largest BST in BT

Here given code implementation process.

// Java Program 
// Find the size of largest bst in a binary tree

// Binary Tree node
class TreeNode
{
    public int data;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        // Set node value
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
public class BinaryTree
{
    public TreeNode root;
    public int min;
    public int max;
    public int result;
    public boolean status;
    public BinaryTree()
    {
        this.root = null;
        this.min = 0;
        this.max = 0;
        this.result = 0;
        this.status = false;
    }
    public int findMaxBST(TreeNode node)
    {
        if (node != null)
        {
            boolean validLeft = false;
            boolean validRight = false;
            // Reset the max
            this.max = Integer.MIN_VALUE;
            // Visit left subtree
            int x = findMaxBST(node.left);
            if (this.status == true && node.data > this.max)
            {
                // When left subtree is bst
                validLeft = true;
            }
            int m = this.min;
            // Reset the min
            this.min = Integer.MAX_VALUE;
            // Visit right subtree
            int y = findMaxBST(node.right);
            if (this.status == true && node.data < this.min)
            {
                // When right subtree is bst
                validRight = true;
            }
            if (node.data > this.max)
            {
                // Get new max value
                this.max = node.data;
            }
            if (m < this.min)
            {
                // When previous min value is small
                this.min = m;
            }
            if (node.data < this.min)
            {
                // Get new min value
                this.min = node.data;
            }
            if (validLeft == true && validRight == true)
            {
                // When left and right subtree is bst
                if ((x + y + 1) > this.result)
                {
                    // Update result
                    this.result = x + y + 1;
                }
                return x + y + 1;
            }
            else
            {
                this.status = false;
                return 0;
            }
        }
        else
        {
            this.status = true;
            return 0;
        }
    }
    public void maximumSizeBST()
    {
        if (this.root == null)
        {
            this.result = 0;
        }
        else
        {
            // Set default value
            this.min = Integer.MAX_VALUE;
            this.max = Integer.MIN_VALUE;
            this.result = 1;
            this.status = false;
            // Find max size bst
            this.findMaxBST(this.root);
        }
        // Display calculated result
        System.out.println(" Maximum BST subtree size is : " + this.result);
    }
    public static void main(String args[])
    {
        BinaryTree tree = new BinaryTree();
        /* Binary Tree
          -----------------------
               1
             /  \
            3    10
           /    /  \
          2    9    11
              / \    \ 
             5   12   13 
                /  \   \
               10   17  21
        */
        // Add node in binary tree
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(3);
        tree.root.left.left = new TreeNode(2);
        tree.root.right = new TreeNode(10);
        tree.root.right.right = new TreeNode(11);
        tree.root.right.left = new TreeNode(9);
        tree.root.right.left.left = new TreeNode(5);
        tree.root.right.left.right = new TreeNode(12);
        tree.root.right.left.right.right = new TreeNode(17);
        tree.root.right.left.right.left = new TreeNode(10);
        tree.root.right.right.right = new TreeNode(13);
        tree.root.right.right.right.right = new TreeNode(21);
        /*
            Resultant BST
            -------------
              9   
             / \     
            5   12   
               /  \    
              10   17  
            ------------
            Result : 5
        */
        tree.maximumSizeBST();
    }
}

Output

 Maximum BST subtree size is : 5
// Include header file
#include <iostream>
#include <limits.h>
using namespace std;
// C++ Program
// Find the size of largest bst in a binary tree

// Binary Tree node
class TreeNode
{
	public: 
    int data;
	TreeNode *left;
	TreeNode *right;
	TreeNode(int data)
	{
		// Set node value
		this->data = data;
		this->left = NULL;
		this->right = NULL;
	}
};
class BinaryTree
{
	public: 
    TreeNode *root;
	int min;
	int max;
	int result;
	bool status;
	BinaryTree()
	{
		this->root = NULL;
		this->min = 0;
		this->max = 0;
		this->result = 0;
		this->status = false;
	}
	int findMaxBST(TreeNode *node)
	{
		if (node != NULL)
		{
			bool validLeft = false;
			bool validRight = false;
			// Reset the max
			this->max = INT_MIN;
			// Visit left subtree
			int x = this->findMaxBST(node->left);
			if (this->status == true && node->data > this->max)
			{
				// When left subtree is bst
				validLeft = true;
			}
			int m = this->min;
			// Reset the min
			this->min = INT_MAX;
			// Visit right subtree
			int y = this->findMaxBST(node->right);
			if (this->status == true && node->data < this->min)
			{
				// When right subtree is bst
				validRight = true;
			}
			if (node->data > this->max)
			{
				// Get new max value
				this->max = node->data;
			}
			if (m < this->min)
			{
				// When previous min value is small
				this->min = m;
			}
			if (node->data < this->min)
			{
				// Get new min value
				this->min = node->data;
			}
			if (validLeft == true && validRight == true)
			{
				// When left and right subtree is bst
				if ((x + y + 1) > this->result)
				{
					// Update result
					this->result = x + y + 1;
				}
				return x + y + 1;
			}
			else
			{
				this->status = false;
				return 0;
			}
		}
		else
		{
			this->status = true;
			return 0;
		}
	}
	void maximumSizeBST()
	{
		if (this->root == NULL)
		{
			this->result = 0;
		}
		else
		{
			// Set default value
			this->min = INT_MAX;
			this->max = INT_MIN;
			this->result = 1;
			this->status = false;
			// Find max size bst
			this->findMaxBST(this->root);
		}
		// Display calculated result
		cout << " Maximum BST subtree size is : " 
             << this->result << endl;
	}
};
int main()
{
	BinaryTree *tree = new BinaryTree();
	/*
	 Binary Tree
	  -----------------------
	       1
	     /  \
	    3    10
	   /    /  \
	  2    9    11
	      / \    \ 
	     5   12   13 
	        /  \   \
	       10   17  21
	*/
	// Add node in binary tree
	tree->root = new TreeNode(1);
	tree->root->left = new TreeNode(3);
	tree->root->left->left = new TreeNode(2);
	tree->root->right = new TreeNode(10);
	tree->root->right->right = new TreeNode(11);
	tree->root->right->left = new TreeNode(9);
	tree->root->right->left->left = new TreeNode(5);
	tree->root->right->left->right = new TreeNode(12);
	tree->root->right->left->right->right = new TreeNode(17);
	tree->root->right->left->right->left = new TreeNode(10);
	tree->root->right->right->right = new TreeNode(13);
	tree->root->right->right->right->right = new TreeNode(21);
	/*
	    Resultant BST
	    -------------
	      9   
	     / \     
	    5   12   
	       /  \    
	      10   17  
	    ------------
	    Result : 5
	*/
	tree->maximumSizeBST();
	return 0;
}

Output

 Maximum BST subtree size is : 5
// Include namespace system
using System;
// Csharp Program
// Find the size of largest bst in a binary tree

// Binary Tree node
public class TreeNode
{
	public int data;
	public TreeNode left;
	public TreeNode right;
	public TreeNode(int data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public int min;
	public int max;
	public int result;
	public Boolean status;
	public BinaryTree()
	{
		this.root = null;
		this.min = 0;
		this.max = 0;
		this.result = 0;
		this.status = false;
	}
	public int findMaxBST(TreeNode node)
	{
		if (node != null)
		{
			Boolean validLeft = false;
			Boolean validRight = false;
			// Reset the max
			this.max = int.MinValue;
			// Visit left subtree
			int x = this.findMaxBST(node.left);
			if (this.status == true && node.data > this.max)
			{
				// When left subtree is bst
				validLeft = true;
			}
			int m = this.min;
			// Reset the min
			this.min = int.MaxValue;
			// Visit right subtree
			int y = this.findMaxBST(node.right);
			if (this.status == true && node.data < this.min)
			{
				// When right subtree is bst
				validRight = true;
			}
			if (node.data > this.max)
			{
				// Get new max value
				this.max = node.data;
			}
			if (m < this.min)
			{
				// When previous min value is small
				this.min = m;
			}
			if (node.data < this.min)
			{
				// Get new min value
				this.min = node.data;
			}
			if (validLeft == true && validRight == true)
			{
				// When left and right subtree is bst
				if ((x + y + 1) > this.result)
				{
					// Update result
					this.result = x + y + 1;
				}
				return x + y + 1;
			}
			else
			{
				this.status = false;
				return 0;
			}
		}
		else
		{
			this.status = true;
			return 0;
		}
	}
	public void maximumSizeBST()
	{
		if (this.root == null)
		{
			this.result = 0;
		}
		else
		{
			// Set default value
			this.min = int.MaxValue;
			this.max = int.MinValue;
			this.result = 1;
			this.status = false;
			// Find max size bst
			this.findMaxBST(this.root);
		}
		// Display calculated result
		Console.WriteLine(" Maximum BST subtree size is : " + this.result);
	}
	public static void Main(String[] args)
	{
		BinaryTree tree = new BinaryTree();
		/*
		 Binary Tree
		  -----------------------
		       1
		     /  \
		    3    10
		   /    /  \
		  2    9    11
		      / \    \ 
		     5   12   13 
		        /  \   \
		       10   17  21
		*/
		// Add node in binary tree
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(3);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(10);
		tree.root.right.right = new TreeNode(11);
		tree.root.right.left = new TreeNode(9);
		tree.root.right.left.left = new TreeNode(5);
		tree.root.right.left.right = new TreeNode(12);
		tree.root.right.left.right.right = new TreeNode(17);
		tree.root.right.left.right.left = new TreeNode(10);
		tree.root.right.right.right = new TreeNode(13);
		tree.root.right.right.right.right = new TreeNode(21);
		/*
		    Resultant BST
		    -------------
		      9   
		     / \     
		    5   12   
		       /  \    
		      10   17  
		    ------------
		    Result : 5
		*/
		tree.maximumSizeBST();
	}
}

Output

 Maximum BST subtree size is : 5
<?php
// Php Program
// Find the size of largest bst in a binary tree

// Binary Tree node
class TreeNode
{
	public $data;
	public $left;
	public $right;
	public	function __construct($data)
	{
		// Set node value
		$this->data = $data;
		$this->left = NULL;
		$this->right = NULL;
	}
}
class BinaryTree
{
	public $root;
	public $min;
	public $max;
	public $result;
	public $status;
	public	function __construct()
	{
		$this->root = NULL;
		$this->min = 0;
		$this->max = 0;
		$this->result = 0;
		$this->status = false;
	}
	public	function findMaxBST($node)
	{
		if ($node != NULL)
		{
			$validLeft = false;
			$validRight = false;
			// Reset the max
			$this->max = -PHP_INT_MAX;
			// Visit left subtree
			$x = $this->findMaxBST($node->left);
			if ($this->status == true && $node->data > $this->max)
			{
				// When left subtree is bst
				$validLeft = true;
			}
			$m = $this->min;
			// Reset the min
			$this->min = PHP_INT_MAX;
			// Visit right subtree
			$y = $this->findMaxBST($node->right);
			if ($this->status == true && $node->data < $this->min)
			{
				// When right subtree is bst
				$validRight = true;
			}
			if ($node->data > $this->max)
			{
				// Get new max value
				$this->max = $node->data;
			}
			if ($m < $this->min)
			{
				// When previous min value is small
				$this->min = $m;
			}
			if ($node->data < $this->min)
			{
				// Get new min value
				$this->min = $node->data;
			}
			if ($validLeft == true && $validRight == true)
			{
				// When left and right subtree is bst
				if (($x + $y + 1) > $this->result)
				{
					// Update result
					$this->result = $x + $y + 1;
				}
				return $x + $y + 1;
			}
			else
			{
				$this->status = false;
				return 0;
			}
		}
		else
		{
			$this->status = true;
			return 0;
		}
	}
	public	function maximumSizeBST()
	{
		if ($this->root == NULL)
		{
			$this->result = 0;
		}
		else
		{
			// Set default value
			$this->min = PHP_INT_MAX;
			$this->max = -PHP_INT_MAX;
			$this->result = 1;
			$this->status = false;
			// Find max size bst
			$this->findMaxBST($this->root);
		}
		// Display calculated result
		echo(" Maximum BST subtree size is : ".
             $this->result.
			"\n");
	}
}

function main()
{
	$tree = new BinaryTree();
	/*
	 Binary Tree
	  -----------------------
	       1
	     /  \
	    3    10
	   /    /  \
	  2    9    11
	      / \    \ 
	     5   12   13 
	        /  \   \
	       10   17  21
	*/
	// Add node in binary tree
	$tree->root = new TreeNode(1);
	$tree->root->left = new TreeNode(3);
	$tree->root->left->left = new TreeNode(2);
	$tree->root->right = new TreeNode(10);
	$tree->root->right->right = new TreeNode(11);
	$tree->root->right->left = new TreeNode(9);
	$tree->root->right->left->left = new TreeNode(5);
	$tree->root->right->left->right = new TreeNode(12);
	$tree->root->right->left->right->right = new TreeNode(17);
	$tree->root->right->left->right->left = new TreeNode(10);
	$tree->root->right->right->right = new TreeNode(13);
	$tree->root->right->right->right->right = new TreeNode(21);
	/*
	    Resultant BST
	    -------------
	      9   
	     / \     
	    5   12   
	       /  \    
	      10   17  
	    ------------
	    Result : 5
	*/
	$tree->maximumSizeBST();
}
main();

Output

 Maximum BST subtree size is : 5
package main
import "math"
import "fmt"
// Go Program
// Find the size of largest bst in a binary tree

// Binary Tree node
type TreeNode struct {
	data int
	left * TreeNode
	right * TreeNode
}
func getTreeNode(data int) * TreeNode {
	var me *TreeNode = &TreeNode {}
	// Set node value
	me.data = data
	me.left = nil
	me.right = nil
	return me
}
type BinaryTree struct {
	root * TreeNode
	min int
	max int
	result int
	status bool
}
func getBinaryTree() * BinaryTree {
	var me *BinaryTree = &BinaryTree {}
	me.root = nil
	me.min = 0
	me.max = 0
	me.result = 0
	me.status = false
	return me
}
func(this *BinaryTree) findMaxBST(node * TreeNode) int {
	if node != nil {
		var validLeft bool = false
		var validRight bool = false
		// Reset the max
		this.max = math.MinInt64
		// Visit left subtree
		var x int = this.findMaxBST(node.left)
		if this.status == true && node.data > this.max {
			// When left subtree is bst
			validLeft = true
		}
		var m int = this.min
		// Reset the min
		this.min = math.MaxInt64
		// Visit right subtree
		var y int = this.findMaxBST(node.right)
		if this.status == true && node.data < this.min {
			// When right subtree is bst
			validRight = true
		}
		if node.data > this.max {
			// Get new max value
			this.max = node.data
		}
		if m < this.min {
			// When previous min value is small
			this.min = m
		}
		if node.data < this.min {
			// Get new min value
			this.min = node.data
		}
		if validLeft == true && validRight == true {
			// When left and right subtree is bst
			if (x + y + 1) > this.result {
				// Update result
				this.result = x + y + 1
			}
			return x + y + 1
		} else {
			this.status = false
			return 0
		}
	} else {
		this.status = true
		return 0
	}
}
func(this *BinaryTree) maximumSizeBST() {
	if this.root == nil {
		this.result = 0
	} else {
		// Set default value
		this.min = math.MaxInt64
		this.max = math.MinInt64
		this.result = 1
		this.status = false
		// Find max size bst
		this.findMaxBST(this.root)
	}
	// Display calculated result
	fmt.Println(" Maximum BST subtree size is : ", this.result)
}
func main() {
	var tree * BinaryTree = getBinaryTree()
	/*
	 Binary Tree
	  -----------------------
	       1
	     /  \
	    3    10
	   /    /  \
	  2    9    11
	      / \    \ 
	     5   12   13 
	        /  \   \
	       10   17  21
	*/
	// Add node in binary tree
	tree.root = getTreeNode(1)
	tree.root.left = getTreeNode(3)
	tree.root.left.left = getTreeNode(2)
	tree.root.right = getTreeNode(10)
	tree.root.right.right = getTreeNode(11)
	tree.root.right.left = getTreeNode(9)
	tree.root.right.left.left = getTreeNode(5)
	tree.root.right.left.right = getTreeNode(12)
	tree.root.right.left.right.right = getTreeNode(17)
	tree.root.right.left.right.left = getTreeNode(10)
	tree.root.right.right.right = getTreeNode(13)
	tree.root.right.right.right.right = getTreeNode(21)
	/*
	    Resultant BST
	    -------------
	      9   
	     / \     
	    5   12   
	       /  \    
	      10   17  
	    ------------
	    Result : 5
	*/
	tree.maximumSizeBST()
}

Output

 Maximum BST subtree size is : 5
// Node JS Program
// Find the size of largest bst in a binary tree

// Binary Tree node
class TreeNode
{
	constructor(data)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	constructor()
	{
		this.root = null;
		this.min = 0;
		this.max = 0;
		this.result = 0;
		this.status = false;
	}
	findMaxBST(node)
	{
		if (node != null)
		{
			var validLeft = false;
			var validRight = false;
			// Reset the max
			this.max = -Number.MAX_VALUE;
			// Visit left subtree
			var x = this.findMaxBST(node.left);
			if (this.status == true && node.data > this.max)
			{
				// When left subtree is bst
				validLeft = true;
			}
			var m = this.min;
			// Reset the min
			this.min = Number.MAX_VALUE;
			// Visit right subtree
			var y = this.findMaxBST(node.right);
			if (this.status == true && node.data < this.min)
			{
				// When right subtree is bst
				validRight = true;
			}
			if (node.data > this.max)
			{
				// Get new max value
				this.max = node.data;
			}
			if (m < this.min)
			{
				// When previous min value is small
				this.min = m;
			}
			if (node.data < this.min)
			{
				// Get new min value
				this.min = node.data;
			}
			if (validLeft == true && validRight == true)
			{
				// When left and right subtree is bst
				if ((x + y + 1) > this.result)
				{
					// Update result
					this.result = x + y + 1;
				}
				return x + y + 1;
			}
			else
			{
				this.status = false;
				return 0;
			}
		}
		else
		{
			this.status = true;
			return 0;
		}
	}
	maximumSizeBST()
	{
		if (this.root == null)
		{
			this.result = 0;
		}
		else
		{
			// Set default value
			this.min = Number.MAX_VALUE;
			this.max = -Number.MAX_VALUE;
			this.result = 1;
			this.status = false;
			// Find max size bst
			this.findMaxBST(this.root);
		}
		// Display calculated result
		console.log(" Maximum BST subtree size is : " + this.result);
	}
}

function main()
{
	var tree = new BinaryTree();
	/*
	 Binary Tree
	  -----------------------
	       1
	     /  \
	    3    10
	   /    /  \
	  2    9    11
	      / \    \ 
	     5   12   13 
	        /  \   \
	       10   17  21
	*/
	// Add node in binary tree
	tree.root = new TreeNode(1);
	tree.root.left = new TreeNode(3);
	tree.root.left.left = new TreeNode(2);
	tree.root.right = new TreeNode(10);
	tree.root.right.right = new TreeNode(11);
	tree.root.right.left = new TreeNode(9);
	tree.root.right.left.left = new TreeNode(5);
	tree.root.right.left.right = new TreeNode(12);
	tree.root.right.left.right.right = new TreeNode(17);
	tree.root.right.left.right.left = new TreeNode(10);
	tree.root.right.right.right = new TreeNode(13);
	tree.root.right.right.right.right = new TreeNode(21);
	/*
	    Resultant BST
	    -------------
	      9   
	     / \     
	    5   12   
	       /  \    
	      10   17  
	    ------------
	    Result : 5
	*/
	tree.maximumSizeBST();
}
main();

Output

 Maximum BST subtree size is : 5
import sys
#  Python 3 Program
#  Find the size of largest bst in a binary tree

#  Binary Tree node
class TreeNode :
	def __init__(self, data) :
		#  Set node value
		self.data = data
		self.left = None
		self.right = None
	

class BinaryTree :
	def __init__(self) :
		self.root = None
		self.min = 0
		self.max = 0
		self.result = 0
		self.status = False
	
	def findMaxBST(self, node) :
		if (node != None) :
			validLeft = False
			validRight = False
			#  Reset the max
			self.max = -sys.maxsize
			#  Visit left subtree
			x = self.findMaxBST(node.left)
			if (self.status == True and node.data > self.max) :
				#  When left subtree is bst
				validLeft = True
			
			m = self.min
			#  Reset the min
			self.min = sys.maxsize
			#  Visit right subtree
			y = self.findMaxBST(node.right)
			if (self.status == True and node.data < self.min) :
				#  When right subtree is bst
				validRight = True
			
			if (node.data > self.max) :
				#  Get new max value
				self.max = node.data
			
			if (m < self.min) :
				#  When previous min value is small
				self.min = m
			
			if (node.data < self.min) :
				#  Get new min value
				self.min = node.data
			
			if (validLeft == True and validRight == True) :
				#  When left and right subtree is bst
				if ((x + y + 1) > self.result) :
					#  Update result
					self.result = x + y + 1
				
				return x + y + 1
			else :
				self.status = False
				return 0
			
		else :
			self.status = True
			return 0
		
	
	def maximumSizeBST(self) :
		if (self.root == None) :
			self.result = 0
		else :
			#  Set default value
			self.min = sys.maxsize
			self.max = -sys.maxsize
			self.result = 1
			self.status = False
			#  Find max size bst
			self.findMaxBST(self.root)
		
		#  Display calculated result
		print(" Maximum BST subtree size is : ", self.result)
	

def main() :
	tree = BinaryTree()
	# Binary Tree
	#  -----------------------
	#       1
	#     /  \
	#    3    10
	#   /    /  \
	#  2    9    11
	#      / \    \ 
	#     5   12   13 
	#        /  \   \
	#       10   17  21
	#  Add node in binary tree
	tree.root = TreeNode(1)
	tree.root.left = TreeNode(3)
	tree.root.left.left = TreeNode(2)
	tree.root.right = TreeNode(10)
	tree.root.right.right = TreeNode(11)
	tree.root.right.left = TreeNode(9)
	tree.root.right.left.left = TreeNode(5)
	tree.root.right.left.right = TreeNode(12)
	tree.root.right.left.right.right = TreeNode(17)
	tree.root.right.left.right.left = TreeNode(10)
	tree.root.right.right.right = TreeNode(13)
	tree.root.right.right.right.right = TreeNode(21)
	#    Resultant BST
	#    -------------
	#      9   
	#     / \     
	#    5   12   
	#       /  \    
	#      10   17  
	#    ------------
	#    Result : 5
	tree.maximumSizeBST()

if __name__ == "__main__": main()

Output

 Maximum BST subtree size is :  5
#  Ruby Program
#  Find the size of largest bst in a binary tree

#  Binary Tree node
class TreeNode 
	# Define the accessor and reader of class TreeNode
	attr_reader :data, :left, :right
	attr_accessor :data, :left, :right
	def initialize(data) 
		#  Set node value
		self.data = data
		self.left = nil
		self.right = nil
	end

end

class BinaryTree 
	# Define the accessor and reader of class BinaryTree
	attr_reader :root, :min, :max, :result, :status
	attr_accessor :root, :min, :max, :result, :status
	def initialize() 
		self.root = nil
		self.min = 0
		self.max = 0
		self.result = 0
		self.status = false
	end

	def findMaxBST(node) 
		if (node != nil) 
			validLeft = false
			validRight = false
			#  Reset the max
			self.max = -(2 ** (0. size * 8 - 2))
			#  Visit left subtree
			x = self.findMaxBST(node.left)
			if (self.status == true && node.data > self.max) 
				#  When left subtree is bst
				validLeft = true
			end

			m = self.min
			#  Reset the min
			self.min = (2 ** (0. size * 8 - 2))
			#  Visit right subtree
			y = self.findMaxBST(node.right)
			if (self.status == true && node.data < self.min) 
				#  When right subtree is bst
				validRight = true
			end

			if (node.data > self.max) 
				#  Get new max value
				self.max = node.data
			end

			if (m < self.min) 
				#  When previous min value is small
				self.min = m
			end

			if (node.data < self.min) 
				#  Get new min value
				self.min = node.data
			end

			if (validLeft == true && validRight == true) 
				#  When left and right subtree is bst
				if ((x + y + 1) > self.result) 
					#  Update result
					self.result = x + y + 1
				end

				return x + y + 1
			else
 
				self.status = false
				return 0
			end

		else
 
			self.status = true
			return 0
		end

	end

	def maximumSizeBST() 
		if (self.root == nil) 
			self.result = 0
		else
 
			#  Set default value
			self.min = (2 ** (0. size * 8 - 2))
			self.max = -(2 ** (0. size * 8 - 2))
			self.result = 1
			self.status = false
			#  Find max size bst
			self.findMaxBST(self.root)
		end

		#  Display calculated result
		print(" Maximum BST subtree size is : ", self.result, "\n")
	end

end

def main() 
	tree = BinaryTree.new()
	# Binary Tree
	#  -----------------------
	#       1
	#     /  \
	#    3    10
	#   /    /  \
	#  2    9    11
	#      / \    \ 
	#     5   12   13 
	#        /  \   \
	#       10   17  21
	#  Add node in binary tree
	tree.root = TreeNode.new(1)
	tree.root.left = TreeNode.new(3)
	tree.root.left.left = TreeNode.new(2)
	tree.root.right = TreeNode.new(10)
	tree.root.right.right = TreeNode.new(11)
	tree.root.right.left = TreeNode.new(9)
	tree.root.right.left.left = TreeNode.new(5)
	tree.root.right.left.right = TreeNode.new(12)
	tree.root.right.left.right.right = TreeNode.new(17)
	tree.root.right.left.right.left = TreeNode.new(10)
	tree.root.right.right.right = TreeNode.new(13)
	tree.root.right.right.right.right = TreeNode.new(21)
	#    Resultant BST
	#    -------------
	#      9   
	#     / \     
	#    5   12   
	#       /  \    
	#      10   17  
	#    ------------
	#    Result : 5
	tree.maximumSizeBST()
end

main()

Output

 Maximum BST subtree size is : 5
// Scala Program
// Find the size of largest bst in a binary tree

// Binary Tree node
class TreeNode(var data: Int,
	var left: TreeNode,
		var right: TreeNode)
{
	def this(data: Int)
	{
		// Set node value
		this(data, null, null);
	}
}
class BinaryTree(var root: TreeNode,
	var min: Int,
		var max: Int,
			var result: Int,
				var status: Boolean)
{
	def this()
	{
		this(null, 0, 0, 0, false);
	}
	def findMaxBST(node: TreeNode): Int = {
		if (node != null)
		{
			var validLeft: Boolean = false;
			var validRight: Boolean = false;
			// Reset the max
			this.max = Int.MinValue;
			// Visit left subtree
			var x: Int = findMaxBST(node.left);
			if (this.status == true && node.data > this.max)
			{
				// When left subtree is bst
				validLeft = true;
			}
			var m: Int = this.min;
			// Reset the min
			this.min = Int.MaxValue;
			// Visit right subtree
			var y: Int = findMaxBST(node.right);
			if (this.status == true && node.data < this.min)
			{
				// When right subtree is bst
				validRight = true;
			}
			if (node.data > this.max)
			{
				// Get new max value
				this.max = node.data;
			}
			if (m < this.min)
			{
				// When previous min value is small
				this.min = m;
			}
			if (node.data < this.min)
			{
				// Get new min value
				this.min = node.data;
			}
			if (validLeft == true && validRight == true)
			{
				// When left and right subtree is bst
				if ((x + y + 1) > this.result)
				{
					// Update result
					this.result = x + y + 1;
				}
				return x + y + 1;
			}
			else
			{
				this.status = false;
				return 0;
			}
		}
		else
		{
			this.status = true;
			return 0;
		}
	}
	def maximumSizeBST(): Unit = {
		if (this.root == null)
		{
			this.result = 0;
		}
		else
		{
			// Set default value
			this.min = Int.MaxValue;
			this.max = Int.MinValue;
			this.result = 1;
			this.status = false;
			// Find max size bst
			this.findMaxBST(this.root);
		}
		// Display calculated result
		println(" Maximum BST subtree size is : " + this.result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var tree: BinaryTree = new BinaryTree();
		/*
		 Binary Tree
		  -----------------------
		       1
		     /  \
		    3    10
		   /    /  \
		  2    9    11
		      / \    \ 
		     5   12   13 
		        /  \   \
		       10   17  21
		*/
		// Add node in binary tree
		tree.root = new TreeNode(1);
		tree.root.left = new TreeNode(3);
		tree.root.left.left = new TreeNode(2);
		tree.root.right = new TreeNode(10);
		tree.root.right.right = new TreeNode(11);
		tree.root.right.left = new TreeNode(9);
		tree.root.right.left.left = new TreeNode(5);
		tree.root.right.left.right = new TreeNode(12);
		tree.root.right.left.right.right = new TreeNode(17);
		tree.root.right.left.right.left = new TreeNode(10);
		tree.root.right.right.right = new TreeNode(13);
		tree.root.right.right.right.right = new TreeNode(21);
		/*
		    Resultant BST
		    -------------
		      9   
		     / \     
		    5   12   
		       /  \    
		      10   17  
		    ------------
		    Result : 5
		*/
		tree.maximumSizeBST();
	}
}

Output

 Maximum BST subtree size is : 5
// Swift 4 Program
// Find the size of largest bst in a binary tree

// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode? ;
	var right: TreeNode? ;
	init(_ data: Int)
	{
		// Set node value
		self.data = data;
		self.left = nil;
		self.right = nil;
	}
}
class BinaryTree
{
	var root: TreeNode? ;
	var min: Int;
	var max: Int;
	var result: Int;
	var status: Bool;
	init()
	{
		self.root = nil;
		self.min = 0;
		self.max = 0;
		self.result = 0;
		self.status = false;
	}
	func findMaxBST(_ node: TreeNode? ) -> Int
	{
		if (node  != nil)
		{
			var validLeft: Bool = false;
			var validRight: Bool = false;
			// Reset the max
			self.max = Int.min;
			// Visit left subtree
			let x: Int = self.findMaxBST(node!.left);
			if (self.status == true && node!.data > self.max)
			{
				// When left subtree is bst
				validLeft = true;
			}
			let m: Int = self.min;
			// Reset the min
			self.min = Int.max;
			// Visit right subtree
			let y: Int = self.findMaxBST(node!.right);
			if (self.status == true && node!.data < self.min)
			{
				// When right subtree is bst
				validRight = true;
			}
			if (node!.data > self.max)
			{
				// Get new max value
				self.max = node!.data;
			}
			if (m < self.min)
			{
				// When previous min value is small
				self.min = m;
			}
			if (node!.data < self.min)
			{
				// Get new min value
				self.min = node!.data;
			}
			if (validLeft == true && validRight == true)
			{
				// When left and right subtree is bst
				if ((x + y + 1) > self.result)
				{
					// Update result
					self.result = x + y + 1;
				}
				return x + y + 1;
			}
			else
			{
				self.status = false;
				return 0;
			}
		}
		else
		{
			self.status = true;
			return 0;
		}
	}
	func maximumSizeBST()
	{
		if (self.root == nil)
		{
			self.result = 0;
		}
		else
		{
			// Set default value
			self.min = Int.max;
			self.max = Int.min;
			self.result = 1;
			self.status = false;
			// Find max size bst
			let _ = self.findMaxBST(self.root);
		}
		// Display calculated result
		print(" Maximum BST subtree size is : ", self.result);
	}
}
func main()
{
	let tree: BinaryTree = BinaryTree();
	/*
	 Binary Tree
	  -----------------------
	       1
	     /  \
	    3    10
	   /    /  \
	  2    9    11
	      / \    \ 
	     5   12   13 
	        /  \   \
	       10   17  21
	*/
	// Add node in binary tree
	tree.root = TreeNode(1);
	tree.root!.left = TreeNode(3);
	tree.root!.left!.left = TreeNode(2);
	tree.root!.right = TreeNode(10);
	tree.root!.right!.right = TreeNode(11);
	tree.root!.right!.left = TreeNode(9);
	tree.root!.right!.left!.left = TreeNode(5);
	tree.root!.right!.left!.right = TreeNode(12);
	tree.root!.right!.left!.right!.right = TreeNode(17);
	tree.root!.right!.left!.right!.left = TreeNode(10);
	tree.root!.right!.right!.right = TreeNode(13);
	tree.root!.right!.right!.right!.right = TreeNode(21);
	/*
	    Resultant BST
	    -------------
	      9   
	     / \     
	    5   12   
	       /  \    
	      10   17  
	    ------------
	    Result : 5
	*/
	tree.maximumSizeBST();
}
main();

Output

 Maximum BST subtree size is :  5
// Kotlin Program
// Find the size of largest bst in a binary tree

// Binary Tree node
class TreeNode
{
	var data: Int;
	var left: TreeNode ? ;
	var right: TreeNode ? ;
	constructor(data: Int)
	{
		// Set node value
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class BinaryTree
{
	var root: TreeNode ? ;
	var min: Int;
	var max: Int;
	var result: Int;
	var status: Boolean;
	constructor()
	{
		this.root = null;
		this.min = 0;
		this.max = 0;
		this.result = 0;
		this.status = false;
	}
	fun findMaxBST(node: TreeNode ? ): Int
	{
		if (node != null)
		{
			var validLeft: Boolean = false;
			var validRight: Boolean = false;
			// Reset the max
			this.max = Int.MIN_VALUE;
			// Visit left subtree
			val x: Int = this.findMaxBST(node.left);
			if (this.status == true && node.data > this.max)
			{
				// When left subtree is bst
				validLeft = true;
			}
			val m: Int = this.min;
			// Reset the min
			this.min = Int.MAX_VALUE;
			// Visit right subtree
			val y: Int = this.findMaxBST(node.right);
			if (this.status == true && node.data < this.min)
			{
				// When right subtree is bst
				validRight = true;
			}
			if (node.data > this.max)
			{
				// Get new max value
				this.max = node.data;
			}
			if (m < this.min)
			{
				// When previous min value is small
				this.min = m;
			}
			if (node.data < this.min)
			{
				// Get new min value
				this.min = node.data;
			}
			if (validLeft == true && validRight == true)
			{
				// When left and right subtree is bst
				if ((x + y + 1) > this.result)
				{
					// Update result
					this.result = x + y + 1;
				}
				return x + y + 1;
			}
			else
			{
				this.status = false;
				return 0;
			}
		}
		else
		{
			this.status = true;
			return 0;
		}
	}
	fun maximumSizeBST(): Unit
	{
		if (this.root == null)
		{
			this.result = 0;
		}
		else
		{
			// Set default value
			this.min = Int.MAX_VALUE;
			this.max = Int.MIN_VALUE;
			this.result = 1;
			this.status = false;
			// Find max size bst
			this.findMaxBST(this.root);
		}
		// Display calculated result
		println(" Maximum BST subtree size is : " + this.result);
	}
}
fun main(args: Array < String > ): Unit
{
	val tree: BinaryTree = BinaryTree();
	/*
	 Binary Tree
	  -----------------------
	       1
	     /  \
	    3    10
	   /    /  \
	  2    9    11
	      / \    \ 
	     5   12   13 
	        /  \   \
	       10   17  21
	*/
	// Add node in binary tree
	tree.root = TreeNode(1);
	tree.root?.left = TreeNode(3);
	tree.root?.left?.left = TreeNode(2);
	tree.root?.right = TreeNode(10);
	tree.root?.right?.right = TreeNode(11);
	tree.root?.right?.left = TreeNode(9);
	tree.root?.right?.left?.left = TreeNode(5);
	tree.root?.right?.left?.right = TreeNode(12);
	tree.root?.right?.left?.right?.right = TreeNode(17);
	tree.root?.right?.left?.right?.left = TreeNode(10);
	tree.root?.right?.right?.right = TreeNode(13);
	tree.root?.right?.right?.right?.right = TreeNode(21);
	/*
	    Resultant BST
	    -------------
	      9   
	     / \     
	    5   12   
	       /  \    
	      10   17  
	    ------------
	    Result : 5
	*/
	tree.maximumSizeBST();
}

Output

 Maximum BST subtree size is : 5


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved