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.
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 : 5package 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 : 5import 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