How to Maxmize Profits to Robbering in a Binary Tree using Dynamic Programming Algorithm?

The thief has found himself a new place for his thievery again. There is only one entrance to this area, called the “root.” Besides the root, each house has one and only one parent house. After a tour, the smart thief realized that “all houses in this place forms a binary tree”. It will automatically contact the police if two directly-linked houses were broken into on the same night.

Determine the maximum amount of money the thief can rob tonight without alerting the police.

Example 1:

Input: [3,2,3,null,3,null,1]

     3
    / \
   2   3
    \   \ 
     3   1

Output: 7
Explanation: Maximum amount of money the thief can rob = 3 + 3 + 1 = 7.
Example 2:

Input: [3,4,5,1,3,null,1]

     3
    / \
   4   5
  / \   \ 
 1   3   1

Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

This puzzle is quite similar to this one where it is considered the 1 dimension of the problem i.e. neighbor nodes cannot be taken at the same time and we need to find out the maximum. In this problem, the domain has been expanded to a binary tree where adjacent nodes cannot be picked at the same time.

Largest Sum of Non-Adjacent Nodes in Binary Tree via Depth First Search Algorithm

Starting from the root of the tree, you can go either left or right. You can sum up the maximum values along the direction when you go from the leaves to the root. Let’s define a function F(T, t) that denote the maximum value from the node T to its sub-trees. The parameter t specifies whether the current node is taken (t=0, ignored, t=1 taken). It is easy to obtain the following:

where is the value of current node;
is the left subtree and is the right node.

Based on this, we write a naive DFS search in the form of recursion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
 
class Solution {
public:
    int search(TreeNode* root, int taken) {
        if (root == NULL) {
            return 0;
        }
        int val = root->val * taken;
        int r = val;
        int next = 1 - taken;
        if (root->left != NULL) {
            r += max(search(root->left, next), search(root->left, 0));
        }
        if (root->right != NULL) {
            r += max(search(root->right, next), search(root->right, 0));
        }
        return r;
    }
 
    int rob(TreeNode* root) {
        int a = search(root, 0);
        int b = search(root, 1);
        return a > b ? a : b;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    int search(TreeNode* root, int taken) {
        if (root == NULL) {
            return 0;
        }
        int val = root->val * taken;
        int r = val;
        int next = 1 - taken;
        if (root->left != NULL) {
            r += max(search(root->left, next), search(root->left, 0));
        }
        if (root->right != NULL) {
            r += max(search(root->right, next), search(root->right, 0));
        }
        return r;
    }

    int rob(TreeNode* root) {
        int a = search(root, 0);
        int b = search(root, 1);
        return a > b ? a : b;
    }
};

This passes the first few small tests but gives a Time Exceeded because it is not efficient at all. Intermediate results are not saved, and calculated over and over again. In some cases, if the next node should not be taken (because current node is taken), then the

1
2

max(search(root->left, next), search(root->left, 0));
max(search(root->right, next), search(root->right, 0));

max(search(root->left, next), search(root->left, 0));
max(search(root->right, next), search(root->right, 0));

are calculated twice.

Largest Sum of Non-Adjacent Nodes in Binary Tree via Dynamic Programming Algorithm (Recursion with Memoziation)

This problem can be solved by DP, because the solution to the sub-problems form the overall solution (“optimal substructure” + “overlapping of subproblems”). The above DFS is slow because intermediate results are computed repeatedly. We can use a map structure to store such results, which transforms to a straightforward DP implementation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
public:
    // cached[0] for not taking the current node
    // cached[1] for taking the current node
    unordered_map<TreeNode*, int> cached[2];
    
    int search(TreeNode* root, int taken) {
        if (root == NULL) {
            return 0;
        }
        TreeNode* key = root;
        if (cached[taken].find(key) != cached[taken].end()) {
            // we calculate this before, so return it
            return cached[taken][key];
        }
        int next = 1 - taken;
        int val = root->val * taken;
        int r = val;
        if (root->left != NULL) {
            r += max(search(root->left, next), search(root->left, 0));
        }
        if (root->right != NULL) {
            r += max(search(root->right, next), search(root->right, 0));
        }
        // storing the answer before returning it.
        cached[taken][key] = r;
        return r;
    }
 
    int rob(TreeNode* root) {
        int a = search(root, 0);
        int b = search(root, 1);
        return a > b ? a : b;
    }
};

class Solution {
public:
    // cached[0] for not taking the current node
    // cached[1] for taking the current node
    unordered_map<TreeNode*, int> cached[2];
    
    int search(TreeNode* root, int taken) {
        if (root == NULL) {
            return 0;
        }
        TreeNode* key = root;
        if (cached[taken].find(key) != cached[taken].end()) {
            // we calculate this before, so return it
            return cached[taken][key];
        }
        int next = 1 - taken;
        int val = root->val * taken;
        int r = val;
        if (root->left != NULL) {
            r += max(search(root->left, next), search(root->left, 0));
        }
        if (root->right != NULL) {
            r += max(search(root->right, next), search(root->right, 0));
        }
        // storing the answer before returning it.
        cached[taken][key] = r;
        return r;
    }

    int rob(TreeNode* root) {
        int a = search(root, 0);
        int b = search(root, 1);
        return a > b ? a : b;
    }
};

Please note that the key should consist of the TreeNode and whether this node is taken or not. At the root level, the answer is simply by comparing two situations: take the root or not to take. This solution passes 124 test cases in 44ms.

Largest Sum of Non-Adjacent Nodes in Binary Tree via the Improved/Optimal Solution

We don’t need to store the results, instead, we use two references variable to pass the results along the search path.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
public:
    void dfs(TreeNode* root, int& has, int& nohas) {
        has = root->val;
        nohas = 0;
        if (root->left) {
            int lhas, lnohas;
            dfs(root->left, lhas, lnohas);
            has += lnohas; // next node is not taken;
            nohas += max(lhas, lnohas); // next node can be taken or not taken
        }
        if (root->right) {
            int rhas, rnohas;
            dfs(root->right, rhas, rnohas);
            has += rnohas; // next node is not taken;
            nohas += max(rhas, rnohas); // next node can be taken or not taken
        }
    }
    
    int rob(TreeNode* root) {
        if (root == NULL) return 0;
        int has, nohas;
        dfs(root, has, nohas);
        return max(has, nohas);
    }
};

class Solution {
public:
    void dfs(TreeNode* root, int& has, int& nohas) {
        has = root->val;
        nohas = 0;
        if (root->left) {
            int lhas, lnohas;
            dfs(root->left, lhas, lnohas);
            has += lnohas; // next node is not taken;
            nohas += max(lhas, lnohas); // next node can be taken or not taken
        }
        if (root->right) {
            int rhas, rnohas;
            dfs(root->right, rhas, rnohas);
            has += rnohas; // next node is not taken;
            nohas += max(rhas, rnohas); // next node can be taken or not taken
        }
    }
    
    int rob(TreeNode* root) {
        if (root == NULL) return 0;
        int has, nohas;
        dfs(root, has, nohas);
        return max(has, nohas);
    }
};

This approach consumes 12ms, almost 4 times faster than the above DP solution that uses map to store the intermediate results.

Largest Sum of Non-Adjacent Numbers (House Robber or Disappearing Coins): Dynamic Programming Algorithms

• Teaching Kids Programming – Dynamic Programming Algorithms to Compute the Maximum Non-Adjacent Tree Sum
• C++ Dynamic Programming Algorithm to Compute the Largest Sum of Non-Adjacent Numbers in a Circular Array
• How to Maxmize Profits to Robbering in a Binary Tree using Dynamic Programming Algorithm?
• Using the Dynamic Programming Algorithm, the Depth First Search or Breadth First Search to Solve House Robber Problem
• Teaching Kids Programming – Largest Sum of Non-Adjacent Numbers (2D Version – Disappearing Coins in a Matrix)

–EOF (The Ultimate Computing & Technology Blog) —