Maximum independent set problem using recursion

Here given code implementation process.

``````/*
Java program for
Maximum independent set problem using recursion
*/
// 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 BinaryTree()
{
this.root = null;
}
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public int maxIndependentSet(TreeNode node)
{
if (node == null)
{
return 0;
}
int a = maxIndependentSet(node.left) +
maxIndependentSet(node.right);
int b = 1;
if (node.left != null)
{
// When node left child are not null
b += maxIndependentSet(node.left.left) +
maxIndependentSet(node.left.right);
}
if (node.right != null)
{
// When node right child are not null
b += maxIndependentSet(node.right.left) +
maxIndependentSet(node.right.right);
}
return maxValue(a, b);
}
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
/*
Binary Tree
-----------------------
1
/  \
3    10
/    /  \
2    9    11
/ \    \
5   12   13
\
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.right.right = new TreeNode(13);
tree.root.right.right.right.right = new TreeNode(21);
// Resultant node is [1,2,5,12,11,21]
// Result : 6
System.out.println(tree.maxIndependentSet(tree.root));
}
}``````

Output

``6``
``````// Include header file
#include <iostream>

using namespace std;
/*
C++ program for
Maximum independent set problem using recursion
*/
// 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;
BinaryTree()
{
this->root = NULL;
}
int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
int maxIndependentSet(TreeNode *node)
{
if (node == NULL)
{
return 0;
}
int a = this->maxIndependentSet(node->left) +
this->maxIndependentSet(node->right);
int b = 1;
if (node->left != NULL)
{
// When node left child are not null
b += this->maxIndependentSet(node->left->left) +
this->maxIndependentSet(node->left->right);
}
if (node->right != NULL)
{
// When node right child are not null
b += this->maxIndependentSet(node->right->left) +
this->maxIndependentSet(node->right->right);
}
return this->maxValue(a, b);
}
};
int main()
{
BinaryTree *tree = new BinaryTree();
/*
Binary Tree
-----------------------
1
/  \
3    10
/    /  \
2    9    11
/ \    \
5   12   13
\
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->right->right = new TreeNode(13);
tree->root->right->right->right->right = new TreeNode(21);
// Resultant node is [1,2,5,12,11,21]
// Result : 6
cout << tree->maxIndependentSet(tree->root) << endl;
return 0;
}``````

Output

``6``
``````// Include namespace system
using System;
/*
Csharp program for
Maximum independent set problem using recursion
*/
// 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 BinaryTree()
{
this.root = null;
}
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public int maxIndependentSet(TreeNode node)
{
if (node == null)
{
return 0;
}
int a = this.maxIndependentSet(node.left) +
this.maxIndependentSet(node.right);
int b = 1;
if (node.left != null)
{
// When node left child are not null
b += this.maxIndependentSet(node.left.left) +
this.maxIndependentSet(node.left.right);
}
if (node.right != null)
{
// When node right child are not null
b += this.maxIndependentSet(node.right.left) +
this.maxIndependentSet(node.right.right);
}
return this.maxValue(a, b);
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
Binary Tree
-----------------------
1
/  \
3    10
/    /  \
2    9    11
/ \    \
5   12   13
\
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.right.right = new TreeNode(13);
tree.root.right.right.right.right = new TreeNode(21);
// Resultant node is [1,2,5,12,11,21]
// Result : 6
Console.WriteLine(tree.maxIndependentSet(tree.root));
}
}``````

Output

``6``
``````package main
import "fmt"
/*
Go program for
Maximum independent set problem using recursion
*/
// 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
}
func getBinaryTree() * BinaryTree {
var me *BinaryTree = &BinaryTree {}
me.root = nil
return me
}
func(this BinaryTree) maxValue(a, b int) int {
if a > b {
return a
}
return b
}
func(this BinaryTree) maxIndependentSet(node * TreeNode) int {
if node == nil {
return 0
}
var a int = this.maxIndependentSet(node.left) +
this.maxIndependentSet(node.right)
var b int = 1
if node.left != nil {
// When node left child are not null
b += this.maxIndependentSet(node.left.left) +
this.maxIndependentSet(node.left.right)
}
if node.right != nil {
// When node right child are not null
b += this.maxIndependentSet(node.right.left) +
this.maxIndependentSet(node.right.right)
}
return this.maxValue(a, b)
}
func main() {
var tree * BinaryTree = getBinaryTree()
/*
Binary Tree
-----------------------
1
/  \
3    10
/    /  \
2    9    11
/ \    \
5   12   13
\
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.right.right = getTreeNode(13)
tree.root.right.right.right.right = getTreeNode(21)
// Resultant node is [1,2,5,12,11,21]
// Result : 6
fmt.Println(tree.maxIndependentSet(tree.root))
}``````

Output

``6``
``````<?php
/*
Php program for
Maximum independent set problem using recursion
*/
// 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	function __construct()
{
\$this->root = NULL;
}
public	function maxValue(\$a, \$b)
{
if (\$a > \$b)
{
return \$a;
}
return \$b;
}
public	function maxIndependentSet(\$node)
{
if (\$node == NULL)
{
return 0;
}
\$a = \$this->maxIndependentSet(\$node->left) +
\$this->maxIndependentSet(\$node->right);
\$b = 1;
if (\$node->left != NULL)
{
// When node left child are not null
\$b += \$this->maxIndependentSet(\$node->left->left) +
\$this->maxIndependentSet(\$node->left->right);
}
if (\$node->right != NULL)
{
// When node right child are not null
\$b += \$this->maxIndependentSet(\$node->right->left) +
\$this->maxIndependentSet(\$node->right->right);
}
return \$this->maxValue(\$a, \$b);
}
}

function main()
{
\$tree = new BinaryTree();
/*
Binary Tree
-----------------------
1
/  \
3    10
/    /  \
2    9    11
/ \    \
5   12   13
\
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->right->right = new TreeNode(13);
\$tree->root->right->right->right->right = new TreeNode(21);
// Resultant node is [1,2,5,12,11,21]
// Result : 6
echo(\$tree->maxIndependentSet(\$tree->root)."\n");
}
main();``````

Output

``6``
``````/*
Node JS program for
Maximum independent set problem using recursion
*/
// 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;
}
maxValue(a, b)
{
if (a > b)
{
return a;
}
return b;
}
maxIndependentSet(node)
{
if (node == null)
{
return 0;
}
var a = this.maxIndependentSet(node.left) +
this.maxIndependentSet(node.right);
var b = 1;
if (node.left != null)
{
// When node left child are not null
b += this.maxIndependentSet(node.left.left) +
this.maxIndependentSet(node.left.right);
}
if (node.right != null)
{
// When node right child are not null
b += this.maxIndependentSet(node.right.left) +
this.maxIndependentSet(node.right.right);
}
return this.maxValue(a, b);
}
}

function main()
{
var tree = new BinaryTree();
/*
Binary Tree
-----------------------
1
/  \
3    10
/    /  \
2    9    11
/ \    \
5   12   13
\
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.right.right = new TreeNode(13);
tree.root.right.right.right.right = new TreeNode(21);
// Resultant node is [1,2,5,12,11,21]
// Result : 6
console.log(tree.maxIndependentSet(tree.root));
}
main();``````

Output

``6``
``````#    Python 3 program for
#    Maximum independent set problem using recursion

#  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

def maxValue(self, a, b) :
if (a > b) :
return a

return b

def maxIndependentSet(self, node) :
if (node == None) :
return 0

a = self.maxIndependentSet(
node.left) + self.maxIndependentSet(node.right)
b = 1
if (node.left != None) :
#  When node left child are not null
b += self.maxIndependentSet(
node.left.left) + self.maxIndependentSet(node.left.right)

if (node.right != None) :
#  When node right child are not null
b += self.maxIndependentSet(
node.right.left) + self.maxIndependentSet(node.right.right)

return self.maxValue(a, b)

def main() :
tree = BinaryTree()
# Binary Tree
#  -----------------------
#       1
#     /  \
#    3    10
#   /    /  \
#  2    9    11
#      / \    \
#     5   12   13
#               \
#                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.right.right = TreeNode(13)
tree.root.right.right.right.right = TreeNode(21)
#  Resultant node is [1,2,5,12,11,21]
#  Result : 6
print(tree.maxIndependentSet(tree.root))

if __name__ == "__main__": main()``````

Output

``6``
``````#    Ruby program for
#    Maximum independent set problem using recursion

#  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_accessor :root
def initialize()
self.root = nil
end

def maxValue(a, b)
if (a > b)
return a
end

return b
end

def maxIndependentSet(node)
if (node == nil)
return 0
end

a = self.maxIndependentSet(node.left) +
self.maxIndependentSet(node.right)
b = 1
if (node.left != nil)
#  When node left child are not null
b += self.maxIndependentSet(node.left.left) +
self.maxIndependentSet(node.left.right)
end

if (node.right != nil)
#  When node right child are not null
b += self.maxIndependentSet(node.right.left) +
self.maxIndependentSet(node.right.right)
end

return self.maxValue(a, b)
end

end

def main()
tree = BinaryTree.new()
# Binary Tree
#  -----------------------
#       1
#     /  \
#    3    10
#   /    /  \
#  2    9    11
#      / \    \
#     5   12   13
#               \
#                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.right.right = TreeNode.new(13)
tree.root.right.right.right.right = TreeNode.new(21)
#  Resultant node is [1,2,5,12,11,21]
#  Result : 6
print(tree.maxIndependentSet(tree.root), "\n")
end

main()``````

Output

``````6
``````
``````/*
Scala program for
Maximum independent set problem using recursion
*/
// 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)
{
def this()
{
this(null);
}
def maxValue(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
return b;
}
def maxIndependentSet(node: TreeNode): Int = {
if (node == null)
{
return 0;
}
var a: Int = maxIndependentSet(node.left) +
maxIndependentSet(node.right);
var b: Int = 1;
if (node.left != null)
{
// When node left child are not null
b += maxIndependentSet(node.left.left) +
maxIndependentSet(node.left.right);
}
if (node.right != null)
{
// When node right child are not null
b += maxIndependentSet(node.right.left) +
maxIndependentSet(node.right.right);
}
return maxValue(a, b);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
Binary Tree
-----------------------
1
/  \
3    10
/    /  \
2    9    11
/ \    \
5   12   13
\
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.right.right = new TreeNode(13);
tree.root.right.right.right.right = new TreeNode(21);
// Resultant node is [1,2,5,12,11,21]
// Result : 6
println(tree.maxIndependentSet(tree.root));
}
}``````

Output

``6``
``````/*
Swift 4 program for
Maximum independent set problem using recursion
*/
// 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? ;
init()
{
self.root = nil;
}
func maxValue(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
return b;
}
func maxIndependentSet(_ node: TreeNode? ) -> Int
{
if (node == nil)
{
return 0;
}
let a: Int = self.maxIndependentSet(node!.left) +
self.maxIndependentSet(node!.right);
var b: Int = 1;
if (node!.left  != nil)
{
// When node left child are not null
b += self.maxIndependentSet(node!.left!.left) +
self.maxIndependentSet(node!.left!.right);
}
if (node!.right  != nil)
{
// When node right child are not null
b += self.maxIndependentSet(node!.right!.left) +
self.maxIndependentSet(node!.right!.right);
}
return self.maxValue(a, b);
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
Binary Tree
-----------------------
1
/  \
3    10
/    /  \
2    9    11
/ \    \
5   12   13
\
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!.right!.right = TreeNode(13);
tree.root!.right!.right!.right!.right = TreeNode(21);
// Resultant node is [1,2,5,12,11,21]
// Result : 6
print(tree.maxIndependentSet(tree.root));
}
main();``````

Output

``6``
``````/*
Kotlin program for
Maximum independent set problem using recursion
*/
// 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 ? ;
constructor()
{
this.root = null;
}
fun maxValue(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
return b;
}
fun maxIndependentSet(node: TreeNode ? ): Int
{
if (node == null)
{
return 0;
}
val a: Int = this.maxIndependentSet(node.left) +
this.maxIndependentSet(node.right);
var b: Int = 1;
if (node.left != null)
{
// When node left child are not null
b += this.maxIndependentSet(node.left?.left) +
this.maxIndependentSet(node.left?.right);
}
if (node.right != null)
{
// When node right child are not null
b += this.maxIndependentSet(node.right?.left) +
this.maxIndependentSet(node.right?.right);
}
return this.maxValue(a, b);
}
}
fun main(args: Array < String > ): Unit
{
val tree: BinaryTree = BinaryTree();
/*
Binary Tree
-----------------------
1
/  \
3    10
/    /  \
2    9    11
/ \    \
5   12   13
\
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?.right?.right = TreeNode(13);
tree.root?.right?.right?.right?.right = TreeNode(21);
// Resultant node is [1,2,5,12,11,21]
// Result : 6
println(tree.maxIndependentSet(tree.root));
}``````

Output

``6``

Comment

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.