Maximum Independent Set Problem
Given a binary tree, find the size of the Maximum Independent Set (MIS) in it.
An independent set is a set of nodes in a binary tree, no two of which are adjacent, i.e., there is no edge connecting any two. The size of an independent set is the total number of nodes it contains. The maximum independent set problem is finding an independent set of the largest possible size for a given binary tree.
For example, the Maximum Independent Set (MIS) of the following binary tree is [1, 4, 6, 7, 8].
From the above example, it is evident that if a node is considered part of MIS, its left and right child cannot be part of MIS. However, its grandchildren can be part of MIS.
The idea is to traverse the binary tree, and for each node in the binary tree, there are two possible cases:
- Exclude the current node from the maximum independent set and process its children.
- Include the current node in the maximum independent set and process its grandchildren.
Accordingly, return the maximum number of nodes possible by either including or excluding the current node. The algorithm can be implemented recursively as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 |
#include <iostream> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Recursive function to find the size of the maximum independent set // for a binary tree int findMISSize(Node* root) { // base case: empty tree if (root == nullptr) { return 0; } // Case 1: Exclude the current node from the maximum independent set and // recur for its left and right child int excl = findMISSize(root->left) + findMISSize(root->right); // Case 2: Include the current node in the maximum independent set and // recur for its grandchildren int incl = 1; if (root->left) { incl += findMISSize(root->left->left) + findMISSize(root->left->right); } if (root->right) { incl += findMISSize(root->right->left) + findMISSize(root->right->right); } // return the maximum number of nodes possible by either // including or excluding the current node return max(excl, incl); } int main() { Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->right->left = new Node(5); root->right->right = new Node(6); root->right->left->left = new Node(7); root->right->left->right = new Node(8); cout << "The size of a maximum independent set is " << findMISSize(root); return 0; } |
Output:
The size of a maximum independent set is 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
// Data structure to store a binary tree node class Node { int data; Node left, right; Node(int data) { this.data = data; this.left = this.right = null; } } class Main { // Recursive function to find the size of the maximum independent set // for a binary tree public static int findMISSize(Node root) { // base case: empty tree if (root == null) { return 0; } // Case 1: Exclude the current node from the maximum independent set and // recur for its left and right child int excl = findMISSize(root.left) + findMISSize(root.right); // Case 2: Include the current node in the maximum independent set and // recur for its grandchildren int incl = 1; if (root.left != null) { incl += findMISSize(root.left.left) + findMISSize(root.left.right); } if (root.right != null) { incl += findMISSize(root.right.left) + findMISSize(root.right.right); } // return the maximum number of nodes possible by either // including or excluding the current node return Integer.max(excl, incl); } public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.right.left = new Node(5); root.right.right = new Node(6); root.right.left.left = new Node(7); root.right.left.right = new Node(8); System.out.println("The size of a maximum independent set is " + findMISSize(root)); } } |
Output:
The size of a maximum independent set is 5
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
# Data structure to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Recursive function to find the size of the maximum independent set # for a binary tree def findMISSize(root): # base case: empty tree if root is None: return 0 # Case 1: Exclude the current node from the maximum independent set and # recur for its left and right child excl = findMISSize(root.left) + findMISSize(root.right) # Case 2: Include the current node in the maximum independent set and # recur for its grandchildren incl = 1 if root.left: incl += findMISSize(root.left.left) + findMISSize(root.left.right) if root.right: incl += findMISSize(root.right.left) + findMISSize(root.right.right) # return the maximum number of nodes possible by either # including or excluding the current node return max(excl, incl) if __name__ == '__main__': root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.right.left = Node(5) root.right.right = Node(6) root.right.left.left = Node(7) root.right.left.right = Node(8) print('The size of a maximum independent set is', findMISSize(root)) |
Output:
The size of a maximum independent set is 5
The time complexity of the above solution is exponential and requires additional space for the recursion (call stack).
It can be seen that the problem has an optimal substructure since it can be broken down into smaller subproblems, which can further be broken down into yet smaller subproblems, and so on. The problem also exhibits overlapping subproblems, so we will end up solving the same subproblem over and over again.
We know that problems having optimal substructure and overlapping subproblems can be solved by dynamic programming, in which subproblem solutions are memoized to avoid recomputation of the same subproblems. The dynamic programming solution can be implemented as follows in C++, Java, and Python:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 |
#include <iostream> #include <unordered_map> using namespace std; // Data structure to store a binary tree node struct Node { int data; Node *left, *right; Node(int data) { this->data = data; this->left = this->right = nullptr; } }; // Recursive function to find the size of the maximum independent set // for a binary tree int findMISSize(Node* root, unordered_map<Node*, int> map) { // base case: empty tree if (root == nullptr) { return 0; } if (map.find(root) != map.end()) { return map[root]; } // Case 1: Exclude the current node from the maximum independent set and // recur for its left and right child int excl = findMISSize(root->left, map) + findMISSize(root->right, map); // Case 2: Include the current node in the maximum independent set and // recur for its grandchildren int incl = 1; if (root->left) { incl += findMISSize(root->left->left, map) + findMISSize(root->left->right, map); } if (root->right) { incl += findMISSize(root->right->left, map) + findMISSize(root->right->right, map); } // save and return the maximum number of nodes possible by either // including or excluding the current node map[root] = max(excl, incl); return map[root]; } int main() { Node* root = new Node(1); root->left = new Node(2); root->right = new Node(3); root->left->left = new Node(4); root->right->left = new Node(5); root->right->right = new Node(6); root->right->left->left = new Node(7); root->right->left->right = new Node(8); unordered_map<Node*, int> map; cout << "The size of a maximum independent set is " << findMISSize(root, map); return 0; } |
Output:
The size of a maximum independent set is 5
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
import java.util.HashMap; import java.util.Map; // Data structure to store a binary tree node class Node { int data; Node left, right; Node(int data) { this.data = data; this.left = this.right = null; } } class Main { // Recursive function to find the size of the maximum independent set // for a binary tree public static int findMIS(Node root, Map<Node, Integer> map) { // base case: empty tree if (root == null) { return 0; } if (map.get(root) != null) { return map.get(root); } // Case 1: Exclude the current node from the maximum independent set and // recur for its left and right child int excl = findMIS(root.left, map) + findMIS(root.right, map); // Case 2: Include the current node in the maximum independent set and // recur for its grandchildren int incl = 1; if (root.left != null) { incl += findMIS(root.left.left, map) + findMIS(root.left.right, map); } if (root.right != null) { incl += findMIS(root.right.left, map) + findMIS(root.right.right, map); } // save and return the maximum number of nodes possible by either // including or excluding the current node map.put(root, Integer.max(excl, incl)); return map.get(root); } public static void main(String[] args) { Node root = new Node(1); root.left = new Node(2); root.right = new Node(3); root.left.left = new Node(4); root.right.left = new Node(5); root.right.right = new Node(6); root.right.left.left = new Node(7); root.right.left.right = new Node(8); Map<Node, Integer> map = new HashMap<>(); System.out.println("The size of a maximum independent set is " + findMIS(root, map)); } } |
Output:
The size of a maximum independent set is 5
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
# Data structure to store a binary tree node class Node: def __init__(self, data, left=None, right=None): self.data = data self.left = left self.right = right # Recursive function to find the size of the maximum independent set # for a binary tree def findMIS(root, d): # base case: empty tree if root is None: return 0 if root in d: return d[root] # Case 1: Exclude the current node from the maximum independent set and # recur for its left and right child excl = findMIS(root.left, d) + findMIS(root.right, d) # Case 2: Include the current node in the maximum independent set and # recur for its grandchildren incl = 1 if root.left: incl += findMIS(root.left.left, d) + findMIS(root.left.right, d) if root.right: incl += findMIS(root.right.left, d) + findMIS(root.right.right, d) # save and return the maximum number of nodes possible by either # including or excluding the current node d[root] = max(excl, incl) return d[root] if __name__ == '__main__': root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.right.left = Node(5) root.right.right = Node(6) root.right.left.left = Node(7) root.right.left.right = Node(8) d = {} print('The size of a maximum independent set is', findMIS(root, d)) |
Output:
The size of a maximum independent set is 5
The time complexity of the above solution is O(n) and requires O(n) extra space, where n is the total number of nodes in the binary tree.
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)