LeetCode 337 House Robber III - Implementation

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: $O(n)$. Space: $O(h)$ for the recursion stack, where $h$ is the tree height.