Given a binary tree, find the size of the largest independent subset (LISS). A subset of nodes is independent if no two nodes in the subset are directly connected by an edge.
Input:
root =[9,5,11,3,7,null,10,null,4]Output: 4Explanation: One maximum independent subset is[9,3,7,10]. No two chosen nodes are directly connected. Other optimal subsets of size 4 also exist(e.g.[5,11,4,7]is NOT valid because 5-7 are adjacent;[5,11,4] has size 3). Size 4is the maximum.
Array representation is level-order (null for absent children). The tree:
1
2
3
4
5
6
7
9
/ \
5 11
/ \ \
3 7 10
\
4
Some valid independent subsets: [9,3,7,10], [5,11,4] (size 3). The largest has size 4.
Input:
root =[2,1,3]Output: 2Explanation: Optimal sets are [1,3](size 2). We cannot take 2 together with1 or 3 because they are adjacent.
Related LeetCode problem: not an exact match, but House Robber III Problem is closely related (tree DP with non-adjacent constraint, maximizing sum instead of count).
If we include a node v in the independent set, we cannot include its immediate children, but we may include its grandchildren. If we exclude v we are free to include its children. The naive recursion compares these two choices.
For each node v compute two values: incl[v] = size of largest independent set of subtree rooted at v when v is included; excl[v] = size when v is excluded. Then:
incl[v] = 1 + sum(excl[child] for child in children) (if v is included, children cannot be included)
excl[v] = sum(max(incl[child], excl[child]) for child in children) (if v is excluded, each child may be included or excluded)
A post-order traversal computes these values in O(n) time.
⏰ Time complexity: O(n) — single post-order traversal visiting each node once.
🧺 Space complexity: O(h) for recursion stack (or O(n) worst-case for a skewed tree), plus O(1) auxiliary per node if values are returned rather than stored.
Created at: 2018-02-07T09:21:59+01:00
Updated at: 2018-02-07T09:21:59+01:00