A Bit of Understanding About Time Complexity When Using Recursion

Today my sister recommended a problem about trees: House Robber III.

The Problem in Brief

We need the maximum path sum from root to leaves of a binary tree, but two adjacent nodes cannot both be taken.

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

Example 2:
     3
    / \
   4   5
  / \   \ 
 1   3   1
Maximum amount of money the thief can rob = 4 + 5 = 9.

Solution 1

After reading the problem I came up with a method myself:

Because once a node is taken, its children cannot be counted. So for the current root node there are two cases: “can be taken” or “cannot be taken”.

• For the case where the root node cannot be taken: return the sum of the maxima of its left and right subtrees

• For the case where the root node can be taken: return the maximum of “take the current node” and “don’t take the current node”

The program is as follows:

int robMax(TreeNode* r, bool couldUse) {
    if(r == nullptr) return 0;

    if(!couldUse) { // current root node cannot be used
        int left = robMax(r->left, true);
        int right = robMax(r->right, true);
        return left + right;
    }

    // 1. take the current value; neither child may be taken
    // 2. don't take the current value; both children are takeable
    return max( r->val + robMax(r->left, false) + robMax(r->right, false),
                robMax(r->left, true) + robMax(r->right, true));
}

int rob(TreeNode* root) {
    if(root == nullptr) return 0;

    return robMax(root, true);
}

Result

The result was truly tragic:

Solution 2

Because a single function’s return value carries too little information, we have to discuss the takeable and non-takeable cases for every node.

If our function could return a bit more information — also returning the situations of the left and right subtrees — then, thinking this way,

the function returns the maximum of “the root node’s value plus the sums of all subtrees of the left and right subtrees” and “the sum of the maxima of the left and right subtrees”

int robFast(TreeNode* r, int& lMax, int &rMax) {
    if(r == nullptr) return 0;
    int ll = 0;
    int lr = 0;
    int rl = 0;
    int rr = 0;

    lMax = robFast(r->left, ll, lr);
    rMax = robFast(r->right, rl, rr);

    return max(r->val+ ll + lr + rl + rr, lMax + rMax);
}

int rob(TreeNode* root) {
    if(root == nullptr) return 0;

    int l = 0, r = 0;
    return robFast(root, l, r);
}

Result

Some Runtime Analysis

Take the tree shown below as an example:

    3
   / \
  4   5
 / \   \ 
1   3   1

• Method 1:

From the diagram you can see that from the root node down to the leaves, the time complexity of each level grows in a Fibonacci-sequence manner (I admit my own brain couldn’t see it from the diagram — you can analyze a tree shaped like a singly linked list and find that each level’s complexity is the sum of two Fibonacci numbers).

Below is how a linked-list-shaped tree is computed

1            t                      1t + 0f
          /     \
2:     t            f               1t + 1f
     /  \           |
3   t    f          t               2t + 1f
   / \   |         / \
4 t   f  t        t   f             3t + 2f

In the Fibonacci sequence: the sum of the first n terms equals the (n+2)th term minus 1. Proof here: Sum of Sequence of Fibonacci Numbers

This should be an exponential-like increase, so producing such a huge runtime — indeed it does.

• Method 2:

Looking back at solution 2, you can see each node is visited once; the time complexity is strictly O(n).

Some Thoughts

When writing recursive functions, we should squeeze every bit of utility out of each function — that is, return every value that can be returned. Perhaps using these return values can effectively reduce the number of recursive calls, thereby improving performance.

In solution 2 above, the maximum values obtainable from the left and right subtrees were also returned, and the function’s performance improved quite a bit.