House Robber III (On Tree)

🎯

House Robber III (On Tree)

mediumDPAmazonGoogle

Imagine a thief planning to rob houses arranged in a neighborhood shaped like a tree. The thief cannot rob two directly connected houses to avoid alerting the police.

💡 This problem is a classic example of dynamic programming on trees, which can be tricky because unlike arrays, trees have hierarchical structures without linear order. Beginners often struggle to understand how to carry state information up and down the tree and how to avoid recomputation.

📋

Problem Statement

Given a binary tree where each node represents the amount of money stashed in a house, determine the maximum amount of money the thief can rob without robbing two directly connected houses (parent and child). Return the maximum amount of money that can be robbed.

The number of nodes in the tree is in the range [1, 10^5].0 <= Node.val <= 10^4

💡

Example

Input"root = [3,2,3,null,3,null,1]"

Output7

Rob houses with values 3 (root), 3 (right child of left child), and 1 (right child of right child). Total = 3 + 3 + 1 = 7.

Input"root = [3,4,5,1,3,null,1]"

Output9

Rob houses with values 4 and 5. Total = 4 + 5 = 9.

• Single node tree → output is node's value
• All nodes have zero value → output is 0
• Linear tree (like a linked list) → behaves like House Robber I
• Complete binary tree with equal values → choose alternate levels

🔁

Why DP?

Why greedy fails:

A greedy approach that always picks the current node with the highest value fails because it might force skipping large sums in children or grandchildren. For example, picking a parent with value 10 might prevent robbing two children with values 6 and 7, losing a total of 13.

DP state:

dp[node] = (max_if_not_robbed, max_if_robbed) where max_if_not_robbed is the max money if we do NOT rob this node, and max_if_robbed is the max money if we rob this node.

Recurrence:dp[node].rob = node.val + sum of dp[child].not_rob for all children; dp[node].not_rob = sum of max(dp[child].rob, dp[child].not_rob) for all children

If we rob the current node, we cannot rob its children, so we add node's value plus the max money from not robbing children. If we don't rob the current node, we take the max of robbing or not robbing each child.

⚠️

Common Mistakes

Forgetting to skip children when robbing current node

Incorrectly sums values leading to overcounting and wrong answer

✅ Ensure when robbing current node, add only grandchildren's values, not children

Not caching results in recursion

Exponential time leading to TLE

✅ Use memoization or bottom-up DP to store intermediate results

Mixing up the order of post-order traversal

Computes parent before children, leading to missing data and errors

✅ Always compute children before parent in DP on trees

Using node values as keys in memo without node identity

Incorrect caching leading to wrong results if values repeat

✅ Use node references or unique IDs as keys in memo

🧠

Brute Force (Pure Recursion)

💡 This approach explores all possibilities by deciding for each node whether to rob it or not, without caching results. It is important to understand this to grasp the problem's complexity and why optimization is needed.

Intuition

At each node, we try robbing it and skipping its children, or skipping it and robbing its children, then take the maximum.

Algorithm

1. Start at the root node.
2. For each node, recursively compute the max money if we rob it (skip children) and if we don't rob it (consider children).
3. Return the maximum of robbing or not robbing the root.
4. Combine results from subtrees to get the final answer.

💡 The recursion tree grows exponentially because each node branches into two choices, making it hard to track without memoization.

Recurrence:f(node) = max(node.val + sum of f(grandchildren), sum of f(children))

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob(root):
    if not root:
        return 0
    val = root.val
    if root.left:
        val += rob(root.left.left) + rob(root.left.right)
    if root.right:
        val += rob(root.right.left) + rob(root.right.right)
    return max(val, rob(root.left) + rob(root.right))

# Example usage:
# root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
# print(rob(root))  # Output: 7

Line Notes

if not root:Base case: no house means no money

val = root.valStart with robbing current node's value

if root.left:Add grandchildren's values if left child exists

return max(val, rob(root.left) + rob(root.right))Choose max between robbing current node plus grandchildren or robbing children

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int rob(TreeNode root) {
        if (root == null) return 0;
        int val = root.val;
        if (root.left != null) {
            val += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            val += rob(root.right.left) + rob(root.right.right);
        }
        return Math.max(val, rob(root.left) + rob(root.right));
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(3);
        root.right.right = new TreeNode(1);
        Solution sol = new Solution();
        System.out.println(sol.rob(root)); // Output: 7
    }
}

Line Notes

if (root == null) return 0;Base case: no node means no money

int val = root.val;Start with current node's value

if (root.left != null)Check if left child exists to add grandchildren

return Math.max(val, rob(root.left) + rob(root.right));Choose max between robbing current node plus grandchildren or robbing children

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    int rob(TreeNode* root) {
        if (!root) return 0;
        int val = root->val;
        if (root->left) {
            val += rob(root->left->left) + rob(root->left->right);
        }
        if (root->right) {
            val += rob(root->right->left) + rob(root->right->right);
        }
        return max(val, rob(root->left) + rob(root->right));
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(2);
    root->left->right = new TreeNode(3);
    root->right = new TreeNode(3);
    root->right->right = new TreeNode(1);
    Solution sol;
    cout << sol.rob(root) << endl; // Output: 7
    return 0;
}

Line Notes

if (!root) return 0;Base case: no node means no money

int val = root->val;Start with current node's value

if (root->left)Check if left child exists to add grandchildren

return max(val, rob(root->left) + rob(root->right));Choose max between robbing current node plus grandchildren or robbing children

function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function rob(root) {
    if (!root) return 0;
    let val = root.val;
    if (root.left) {
        val += rob(root.left.left) + rob(root.left.right);
    }
    if (root.right) {
        val += rob(root.right.left) + rob(root.right.right);
    }
    return Math.max(val, rob(root.left) + rob(root.right));
}

// Example usage:
// const root = new TreeNode(3, new TreeNode(2, null, new TreeNode(3)), new TreeNode(3, null, new TreeNode(1)));
// console.log(rob(root)); // Output: 7

Line Notes

if (!root) return 0;Base case: no house means no money

let val = root.val;Start with robbing current node's value

if (root.left)Add grandchildren's values if left child exists

return Math.max(val, rob(root.left) + rob(root.right));Choose max between robbing current node plus grandchildren or robbing children

⏱

Complexity

TimeO(2^n)

SpaceO(n) due to recursion stack

Each node branches into two recursive calls for grandchildren and children, leading to exponential calls.

💡 For n=20, this means over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem's structure.

🧠

Top-Down Memoization

💡 Memoization caches results of subproblems to avoid recomputation, drastically improving efficiency while keeping the recursive structure.

Intuition

Store the maximum money for each node once computed, so repeated calls return cached results.

Algorithm

1. Use a hash map to store results for each node.
2. For each node, check if result is cached; if yes, return it.
3. Otherwise, compute max money by robbing or skipping the node recursively.
4. Cache and return the computed result.

💡 Memoization turns exponential recursion into linear by remembering answers.

Recurrence:f(node) = max(node.val + sum of f(grandchildren), sum of f(children)) with memoization

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob(root):
    memo = {}
    def dfs(node):
        if not node:
            return 0
        if node in memo:
            return memo[node]
        val = node.val
        if node.left:
            val += dfs(node.left.left) + dfs(node.left.right)
        if node.right:
            val += dfs(node.right.left) + dfs(node.right.right)
        res = max(val, dfs(node.left) + dfs(node.right))
        memo[node] = res
        return res
    return dfs(root)

# Example usage:
# root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
# print(rob(root))  # Output: 7

Line Notes

memo = {}Initialize cache to store results for nodes

if node in memo:Return cached result if available

val = node.valStart with robbing current node's value

memo[node] = resCache computed result to avoid recomputation

import java.util.HashMap;

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    private HashMap<TreeNode, Integer> memo = new HashMap<>();

    public int rob(TreeNode root) {
        if (root == null) return 0;
        if (memo.containsKey(root)) return memo.get(root);
        int val = root.val;
        if (root.left != null) {
            val += rob(root.left.left) + rob(root.left.right);
        }
        if (root.right != null) {
            val += rob(root.right.left) + rob(root.right.right);
        }
        int res = Math.max(val, rob(root.left) + rob(root.right));
        memo.put(root, res);
        return res;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(3);
        root.right.right = new TreeNode(1);
        Solution sol = new Solution();
        System.out.println(sol.rob(root)); // Output: 7
    }
}

Line Notes

private HashMap<TreeNode, Integer> memo = new HashMap<>();Cache to store results for nodes

if (memo.containsKey(root)) return memo.get(root);Return cached result if available

int val = root.val;Start with current node's value

memo.put(root, res);Cache computed result to avoid recomputation

#include <iostream>
#include <unordered_map>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

struct TreeNodeHash {
    size_t operator()(const TreeNode* node) const {
        return hash<long long>()((long long)node);
    }
};

class Solution {
    unordered_map<TreeNode*, int, TreeNodeHash> memo;
public:
    int rob(TreeNode* root) {
        if (!root) return 0;
        if (memo.count(root)) return memo[root];
        int val = root->val;
        if (root->left) {
            val += rob(root->left->left) + rob(root->left->right);
        }
        if (root->right) {
            val += rob(root->right->left) + rob(root->right->right);
        }
        int res = max(val, rob(root->left) + rob(root->right));
        memo[root] = res;
        return res;
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(2);
    root->left->right = new TreeNode(3);
    root->right = new TreeNode(3);
    root->right->right = new TreeNode(1);
    Solution sol;
    cout << sol.rob(root) << endl; // Output: 7
    return 0;
}

Line Notes

unordered_map<TreeNode*, int, TreeNodeHash> memo;Cache to store results for nodes

if (memo.count(root)) return memo[root];Return cached result if available

int val = root->val;Start with current node's value

memo[root] = res;Cache computed result to avoid recomputation

function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

const memo = new Map();
function rob(root) {
    if (!root) return 0;
    if (memo.has(root)) return memo.get(root);
    let val = root.val;
    if (root.left) {
        val += rob(root.left.left) + rob(root.left.right);
    }
    if (root.right) {
        val += rob(root.right.left) + rob(root.right.right);
    }
    const res = Math.max(val, rob(root.left) + rob(root.right));
    memo.set(root, res);
    return res;
}

// Example usage:
// const root = new TreeNode(3, new TreeNode(2, null, new TreeNode(3)), new TreeNode(3, null, new TreeNode(1)));
// console.log(rob(root)); // Output: 7

Line Notes

const memo = new Map();Cache to store results for nodes

if (memo.has(root)) return memo.get(root);Return cached result if available

let val = root.val;Start with current node's value

memo.set(root, res);Cache computed result to avoid recomputation

⏱

Complexity

TimeO(n)

SpaceO(n) due to recursion stack and memo

Each node is computed once and cached, so linear time.

💡 For n=10^5, this is efficient enough to run within seconds.

Interview Verdict: Accepted

Memoization makes the solution efficient and practical for large inputs.

🧠

Bottom-Up DP with Post-Order Traversal

💡 This approach uses a bottom-up traversal to compute the answer for each node based on its children, avoiding recursion overhead and making the logic clearer.

Intuition

For each node, compute two values: max money if robbed and max money if not robbed, using children's results.

Algorithm

1. Traverse the tree in post-order (children before parent).
2. For each node, compute two values: rob and not_rob.
3. rob = node.val + sum of not_rob from children.
4. not_rob = sum of max(rob, not_rob) from children.
5. Return max of rob and not_rob at root.

💡 This approach cleanly separates the two states per node and uses children's results to build parent's answer.

Recurrence:dp[node].rob = node.val + sum(dp[child].not_rob); dp[node].not_rob = sum(max(dp[child].rob, dp[child].not_rob))

</>

Code

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def rob(root):
    def dfs(node):
        if not node:
            return (0, 0)  # (not_rob, rob)
        left = dfs(node.left)
        right = dfs(node.right)
        rob_node = node.val + left[0] + right[0]
        not_rob_node = max(left) + max(right)
        return (not_rob_node, rob_node)
    return max(dfs(root))

# Example usage:
# root = TreeNode(3, TreeNode(2, None, TreeNode(3)), TreeNode(3, None, TreeNode(1)))
# print(rob(root))  # Output: 7

Line Notes

def dfs(node):Helper function to return tuple (not_rob, rob) for node

if not node:Base case returns zero for both states

rob_node = node.val + left[0] + right[0]Rob current node plus not robbing children

not_rob_node = max(left) + max(right)Don't rob current node, take max of rob or not rob children

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

public class Solution {
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }

    private int[] dfs(TreeNode node) {
        if (node == null) return new int[]{0, 0};
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        int rob = node.val + left[0] + right[0];
        int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return new int[]{notRob, rob};
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(2);
        root.left.right = new TreeNode(3);
        root.right = new TreeNode(3);
        root.right.right = new TreeNode(1);
        Solution sol = new Solution();
        System.out.println(sol.rob(root)); // Output: 7
    }
}

Line Notes

private int[] dfs(TreeNode node)Returns array with two states: notRob and rob

if (node == null) return new int[]{0, 0};Base case returns zero for both states

int rob = node.val + left[0] + right[0];Rob current node plus not robbing children

int notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);Don't rob current node, take max of rob or not rob children

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class Solution {
public:
    pair<int,int> dfs(TreeNode* node) {
        if (!node) return {0,0};
        auto left = dfs(node->left);
        auto right = dfs(node->right);
        int rob = node->val + left.first + right.first;
        int notRob = max(left.first, left.second) + max(right.first, right.second);
        return {notRob, rob};
    }

    int rob(TreeNode* root) {
        auto res = dfs(root);
        return max(res.first, res.second);
    }
};

int main() {
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(2);
    root->left->right = new TreeNode(3);
    root->right = new TreeNode(3);
    root->right->right = new TreeNode(1);
    Solution sol;
    cout << sol.rob(root) << endl; // Output: 7
    return 0;
}

Line Notes

pair<int,int> dfs(TreeNode* node)Returns pair (notRob, rob) for node

if (!node) return {0,0};Base case returns zero for both states

int rob = node->val + left.first + right.first;Rob current node plus not robbing children

int notRob = max(left.first, left.second) + max(right.first, right.second);Don't rob current node, take max of rob or not rob children

function TreeNode(val, left=null, right=null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

function rob(root) {
    function dfs(node) {
        if (!node) return [0, 0];
        const left = dfs(node.left);
        const right = dfs(node.right);
        const rob = node.val + left[0] + right[0];
        const notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        return [notRob, rob];
    }
    const res = dfs(root);
    return Math.max(res[0], res[1]);
}

// Example usage:
// const root = new TreeNode(3, new TreeNode(2, null, new TreeNode(3)), new TreeNode(3, null, new TreeNode(1)));
// console.log(rob(root)); // Output: 7

Line Notes

function dfs(node)Returns array [notRob, rob] for node

if (!node) return [0, 0];Base case returns zero for both states

const rob = node.val + left[0] + right[0];Rob current node plus not robbing children

const notRob = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);Don't rob current node, take max of rob or not rob children

⏱

Complexity

TimeO(n)

SpaceO(n) due to recursion stack

Each node is visited once in post-order traversal.

💡 For n=10^5, this approach is efficient and scalable.

Interview Verdict: Accepted

This is the optimal and cleanest approach for this problem.

📊

All Approaches - One-Glance Tradeoffs

💡 Bottom-up DP with post-order traversal is the best approach to implement in interviews due to clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	No	Mention only - never code
2. Top-Down Memoization	O(n)	O(n) recursion stack + memo	Yes (deep recursion)	Yes	Good to mention and code if comfortable
3. Bottom-Up DP (Post-Order)	O(n)	O(n) recursion stack	Yes (deep recursion)	Yes	Best approach to code in interview

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and learn how to explain your thought process clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints.Step 2: Explain the brute force recursive approach to show understanding.Step 3: Introduce memoization to optimize recursion.Step 4: Present bottom-up DP with post-order traversal as the optimal solution.Step 5: Code the bottom-up DP solution and test with examples.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

Interviewer tests your understanding of tree DP, ability to optimize recursion with memoization, and clarity in explaining state definitions and transitions.

Common Follow-ups

• What if the tree is a linked list? → The problem reduces to House Robber I.
• Can you reconstruct which nodes were robbed? → Yes, by tracking choices during DP.

💡 These follow-ups test your ability to adapt solutions and extend them to practical scenarios.

🔍

Pattern Recognition

When to Use

1) Problem involves trees, 2) Need to optimize choices with constraints on adjacency, 3) Maximize sum or value, 4) Overlapping subproblems exist.

Signature Phrases

cannot rob two directly connected housesmaximum amount of moneybinary tree structure

NOT This Pattern When

Problems involving arbitrary graphs or no adjacency constraints are different and require other techniques.

Similar Problems

House Robber I - linear array version of the problemHouse Robber II - circular array versionBinary Tree Maximum Path Sum - similar tree DP but different constraints

Practice

1. Consider the following code snippet for counting arithmetic subsequences. What is the final returned value when the input is [1, 3, 5]?

easy

A. 1

B. 2

C. 3

D. 0

Solution

1. Step 1: Trace dp and total for input [1,3,5]

   i=1,j=0: diff=2, dp[1][2]=0+1=1, total+=0=0; i=2,j=0: diff=4, dp[2][4]=0+1=1, total+=0=0; i=2,j=1: diff=2, dp[2][2]=dp[1][2]+1=1+1=2, total+=dp[1][2]=1

2. Step 2: Calculate final total

   Total after all iterations is 1, representing one arithmetic subsequence of length ≥ 3: [1,3,5].

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Only one arithmetic subsequence of length ≥ 3 exists [OK]

Hint: Only subsequences length ≥3 count; pairs add to dp but not total [OK]

Common Mistakes:

• Counting pairs as arithmetic subsequences
• Adding dp[i][diff] to total instead of dp[j][diff]

2. Consider the following Python code implementing the optimal solution for the envelope nesting problem. Given the input [[5,4],[6,4],[6,7],[2,3]], what is the value of the list lis after processing all envelopes?

easy

A. [2, 3, 7]

B. [3, 4, 7]

C. [2, 3, 4, 7]

D. [3, 4]

Solution

1. Step 1: Sort envelopes by width ascending and height descending

   Sorted envelopes: [[2,3],[5,4],[6,7],[6,4]] -> heights = [3,4,7,4]

2. Step 2: Build LIS on heights

   Process heights: 3 -> lis=[3]; 4 -> lis=[3,4]; 7 -> lis=[3,4,7]; 4 -> replace lis[1] with 4 (no change). Final lis = [3,4,7]

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Final lis length 3 matches expected output [OK]

Hint: Trace LIS updates carefully with bisect_left [OK]

Common Mistakes:

• Misplacing elements in lis on equal heights
• Confusing bisect_left with bisect_right
• Not sorting heights correctly

3. The following code attempts to count arithmetic subsequences but contains a subtle bug. Identify the line causing incorrect counting of subsequences.

medium

A. dp = [defaultdict(int) for _ in range(n)]

B. count_at_j = dp[j][diff]

C. dp[i][diff] += count_at_j + 1

D. total += dp[i][diff] # adding wrong value to total

Solution

1. Step 1: Understand counting logic

   Total should only increase by count_at_j, which counts subsequences extended by nums[i]. Adding dp[i][diff] counts pairs and subsequences multiple times.

2. Step 2: Identify incorrect line

   Line adding dp[i][diff] to total causes double counting; it should add only count_at_j.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct counting adds count_at_j, not dp[i][diff] [OK]

Hint: Only add count_at_j to total, not dp[i][diff] [OK]

Common Mistakes:

• Adding dp[i][diff] to total
• Not initializing dp correctly
• Counting pairs as subsequences

4. What is the time complexity of the iterative postorder traversal solution for the Binary Tree Maximum Path Sum problem, assuming the tree has n nodes?

medium

A. O(n) for traversal but O(n) extra space for the stack and gains dictionary

B. O(n log n) due to repeated stack operations and subtree recomputations

C. O(n^2) because for each node, the algorithm recomputes gains from all descendants

D. O(n) because each node is visited once and gains are computed in constant time per node

Solution

1. Step 1: Identify traversal cost

   The iterative postorder traversal visits each node exactly once, pushing and popping it from the stack once.

2. Step 2: Analyze per-node computation

   At each node, gains are computed using stored values from children in O(1) time, no recomputation of subtrees.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Linear traversal with constant work per node -> O(n) time [OK]

Hint: Each node processed once, no repeated subtree work [OK]

Common Mistakes:

• Confusing recursion stack with repeated work
• Assuming recomputation of subtree gains
• Ignoring constant time per node

5. Suppose the problem is modified so that the path can reuse nodes multiple times (i.e., cycles allowed), and the tree is now a general graph with possible cycles. Which of the following approaches correctly adapts the maximum path sum solution to handle this variant?

hard

A. Use the same DP on tree approach with memoization, ignoring cycles since the graph is connected

B. Convert the graph to a tree by removing edges to break cycles, then apply the original DP on tree solution

C. Perform a DFS with cycle detection and use dynamic programming with visited states to avoid infinite loops, tracking maximum sums on simple paths

D. Use a greedy approach to select the highest value nodes repeatedly until no improvement

Solution

1. Step 1: Understand the impact of cycles

   Allowing node reuse and cycles means paths can be infinite unless cycles are detected and handled.

2. Step 2: Identify correct approach

   DFS with cycle detection and DP with visited states prevents infinite loops and correctly computes max sums on simple paths in graphs.

3. Step 3: Why other options fail

   Original DP assumes tree structure; greedy ignores path connectivity; converting graph to tree loses valid paths.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Cycle-aware DFS with DP is necessary for graphs with cycles [OK]

Hint: Cycle detection plus DP needed for graphs with cycles [OK]

Common Mistakes:

• Ignoring cycles causes infinite loops
• Greedy fails on path connectivity
• Tree DP invalid on graphs