function rob(root)
function dfs(node)
if node is null then
return (0, 0)
// (rob, skip)
left := dfs(node.left)
right := dfs(node.right)
rob_this := node.val + left.skip + right.skip
skip_this := max(left.rob, left.skip) + max(right.rob, right.skip)
return (rob_this, skip_this)
result := dfs(root)
return max(result.rob, result.skip)
Time: . Each node visited once. Returning a pair avoids storing a separate array. The code implements the recurrence relation directly. corresponds to part of the formula.
To verify your understanding, pick a small example and trace through the code by hand. Write down the value of each variable at each step. This builds intuition that helps When face new problems. Space: for recursion stack and memoization.
Time: . Space: .