324. Largest Independent Set in a Binary Tree

Given a binary tree, find the size of its largest independent set - the largest possible subset of nodes such that no two nodes in the subset are directly connected by an edge (i.e., no subset node is the parent of another subset node). The tree is given as space-separated level-order tokens, where 'N' means no node there: the first token is the root, then for each node dequeued in level order you read its left-child token then its right-child token (if input runs out early, remaining children are treated as N).

Input: The tree is given on a single line as space-separated level-order tokens: the first token is the root, and then for each node dequeued in level order its left-child token then right-child token follow, where 'N' means no node there (missing trailing children are treated as N). Output: Print a single integer - the size of the largest independent set of nodes.

1 <= number of nodes <= 10^4

MEMOIZING per node (rather than naive recursion) is essential - a naive recursive implementation recomputes each node's GRANDCHILDREN'S values repeatedly across different ancestor calls, causing serious inefficiency without this caching.

Find the largest set of nodes in a binary tree such that no two are directly connected by an edge. Brute force: Try every possible subset of nodes directly and check the no-two-adjacent constraint - this is exponential (2^n subsets), impractical for n up to 10^4. Optimised: This is the TREE-STRUCTURED version of 'Maximum Sum Such That No Two Elements Are Adjacent' from earlier in this category - instead of a simple linear array, the 'adjacent' relationship is defined by TREE EDGES, and the recurrence naturally adapts by considering GRANDCHILDREN (skipping one generation) when a node is included, memoizing per node to avoid recomputing the same subtree's answer multiple times.

For every node, recursively consider the two mutually exclusive choices: either the node is included (so neither direct child may be included, but grandchildren still can be) or the node is excluded (so each child subtree is free to make its own best choice), and recompute the best answer for every subtree from scratch every time it's needed, without remembering results already computed for repeated subtrees such as a node's grandchildren. Because the same nodes' independent-set sizes get recomputed many times through different recursive call chains, the running time blows up combinatorially on deep trees. Time: O(2^n) Space: O(h) recursion depth

Do one post-order depth-first traversal where each call returns two numbers for its subtree: the best independent-set size assuming the current node is included, and the best size assuming it is not. A node's 'included' value is 1 plus the sum of its children's 'excluded' values, since an included node forbids its direct children, and its 'excluded' value is the sum of the better of each child's included/excluded values. Combining children's pairs takes constant work per node, so the whole tree is processed in one pass with no separate memo table needed, only the recursion stack. Time: O(n) Space: O(h)

Use the same recursive relation, that the largest independent set rooted at a node is the better of (1 plus the largest independent sets of all four grandchildren) versus (the largest independent sets of the two direct children), but store each node's computed result in a hash map the first time it is computed and simply look it up on any later request. Since each node's answer is now computed exactly once and every recursive call either does O(1) work or hits the memo, the total work becomes linear. Time: O(n) Space: O(n)

1. For each node, define liset(node) as the answer for the subtree rooted there, with two options: INCLUDE it, or EXCLUDE it. 2. EXCLUDING the node: liset(node) = liset(left child) + liset(right child). 3. INCLUDING the node: since its direct children must then be excluded, you get 1 plus the liset values of its GRANDCHILDREN (the children of its left and right child); liset(node) = max of these two options, memoized per node.

Time: O(n) - one single post-order pass, computing each node's liset value exactly once. Space: O(h) for the recursion stack, where h is the tree's height.

Test a tree with a single node (answer 1), a highly skewed tree (essentially a linked list), and the upper bound of 10^4 nodes to confirm memoization avoids recomputation.

Be ready to connect this directly to 'House Robber III' (its well-known alternate name, extending the classic array-based House Robber problem to tree structures) - recognizing this connection to a widely-known problem is a strong signal.