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)
Each node is visited once. Returning a pair avoids storing a separate memo array.
To verify your understanding, pick a small tree and trace through the code by hand. Write down the (rob, skip) pair at each node.
Time: . Space: for the recursion stack, where is the tree height.