Largest Independent Set in a tree
Problem
Return the size of the largest set of tree nodes in which no two nodes are connected by an edge (no parent–child pair). With node values instead of counts, this is House Robber III.
Example 1
Input: 10 with children 20, 30; 20 has children 40, 50; 30 has right child 60; 50 has children 70, 80 Output: 5
{10, 40, 60, 70, 80}.
Also asked as: Largest Independent Set Problem
Test cases
No automated tests for this problem yet. Use the examples above to check your output.
This problem has no automated tests. Run executes your code and shows what it logs.
View solutionHide solution1 approach
1. Tree DP — include vs exclude each node
Time O(n)Space O(h)
inc(node) = 1 + Σ exc(child); exc(node) = Σ max(inc(child), exc(child)). Answer = max(inc(root), exc(root)).
function largestIndependentSet(node) { if (!node) return { inc: 0, exc: 0 }; const L = largestIndependentSet(node.left); const R = largestIndependentSet(node.right); return { inc: 1 + L.exc + R.exc, exc: Math.max(L.inc, L.exc) + Math.max(R.inc, R.exc), };}// answer: const r = largestIndependentSet(root); return Math.max(r.inc, r.exc);