Skip to main content

Maximum independent set problem using recursion

The Maximum Independent Set (MIS) problem is a classic graph theory problem. Given an undirected graph, an independent set is a subset of vertices in which no two vertices are adjacent (i.e., not connected by an edge). The Maximum Independent Set problem aims to find the largest possible independent set in the graph.

In this context, we are solving the Maximum Independent Set problem on a binary tree. The binary tree consists of nodes, each containing an integer value, and has the property that each node can have at most two children - a left child and a right child. The goal is to find the size of the maximum independent set in the given binary tree.

Explanation using Example

Let's consider the binary tree :


    1
   / \
  3   10
 /   /  \
2   9    11
    / \    \
   5   12   13
             \
              21

The maximum independent set for this tree is [1, 2, 5, 12, 11, 21], and its size is 6.

Pseudocode

maxIndependentSet(node)
    if node is null
        return 0
    a = maxIndependentSet(node.left) + maxIndependentSet(node.right)
    b = 1
    if node.left is not null
        b += maxIndependentSet(node.left.left) + maxIndependentSet(node.left.right)
    if node.right is not null
        b += maxIndependentSet(node.right.left) + maxIndependentSet(node.right.right)
    return max(a, b)

Algorithm Explanation

The maxIndependentSet function is a recursive algorithm to find the maximum independent set of the binary tree. It takes a node as input and calculates two values a and b. The variable a represents the size of the independent set excluding the current node's value, while b represents the size of the independent set including the current node's value.

The algorithm calculates a by recursively calling maxIndependentSet on the left and right subtrees and summing up their results. Then, it calculates b by adding 1 (representing the current node) to the maximum independent set sizes of the left and right subtrees' children.

Finally, the algorithm returns the maximum of a and b, which represents the size of the maximum independent set that can be obtained starting from the current node.

Code Solution

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_reader :root
	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

Time Complexity

The time complexity of the provided algorithm is O(2^N), where N is the number of nodes in the binary tree. This is because for each node in the binary tree, the algorithm explores two possibilities (including the node or excluding it) in a depth-first manner. As a result, the number of recursive calls grows exponentially with the number of nodes.

Resultant Output Explanation

The given binary tree's maximum independent set is [1, 2, 5, 12, 11, 21], and its size is 6. The algorithm correctly calculates this result, and the output of the code is 6, as expected.

Last updated on by Kalkicode




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.

New Comment