I am having a very hard time understanding tree based DP problems. I am fairly comfortable with array based DP problems but I cannot come up with the correct thought process for tree based problems and I was hoping somebody could please explain their thought process.
I will talk about my thought process behind array based problems and then explain my troubles with tree based DP problems.
My thought process for array problems
The way I think about DP in array based problems is as follows. Let us consider a problem like Minimum Path Sum. Here the objective is to get from the top left to bottom right positions in a matrix such that we minimize the cost of the path. We can only move left and right.
The way I would approach problems like this is as follows:
- First I would construct a recurrence. In this case the recurrence is as follows
The recurrence is:
f(i, j) = a[i][j] // if i == m and j == n
f(i, j) = a[i][j] + f(i, j+1) // if i == m
f(i, j) = a[i][j] + f(i+1, j) // if j == n
f(i, j) = a[i][j] + Math.min( f(i, j+1), f(i+1, j) ) // Otherwise
Next I look at the equations which tells me the problem can be solved using DP as there are overlapping subproblems in
f(i+1, j) and f(i, j+1)
. There is also an optimal substructure.I can also tell the time/space complexity just by looking at the recurrence.
- Because we must compute all states which is all (i,j) pairs and because time per state is O(1) (adding a[i][j] to result) the time complexity is O(n^2).
- Looking at the recurrence, i depends only on i+1 and not on i+2, i+3 ... similarly j depends only on j+1 and not on j+2, j+3... so we can get away with using only 1 extra row (either i+1 or j+1) instead of the entire matrix so space complexity is O(n).
Hence I would come up with a n^2 time and n space solution. I can do this without any problems.
My thought process for tree problems
However I am having a hard time applying the same thought process to tree based DP problems. As an example let us consider the problem Diameter of Binary Tree where the objective is to find the longest path between any 2 nodes in the tree.
I can come up with a recurrence for this problem which is as follows:
f(n) = 0 // if n == null
f(n) = max( 1+height(n.left) + height(n.right), // longest path passing through root
f(n.left), // longest path in left subtree
f(n.right) ) // longest path in right subtree
Because f(n.left)
for example is computed by doing 1+height(n.left.left) + height(n.left.right)
I can tell that DP must be used.
So my approach would be to create a cache of size 'n' that stores all the heights of the nodes. So the space complexity would be O(n).
However the optimal solution of this problem has a space complexity of O(1) and I am having a hard time figuring that out just by looking at the recurrence. How does the recurrence tell you that space complexity can be reduced and that O(1) space is enough and O(n) is not needed? How do you know what value(s) to store in this case? In array based problems I can get the answers to both these questions just by looking at the recurrence but for tree based dp it is not so obvious to me.
My questions:
What can you tell about this problem just by looking at the recurrence for the tree problem? Putting aside my own thought process, if I gave you this recurrence and nothing else what conclusions would you reach and how would you write the program? I am curious about your thought process.
For array based problems I can tell just by looking at the recurrence both how much space I needed to solve the problem AND what exactly I needed to store (I need to store values of row i+1 in min path sum and nothing else). How can I do the same for the tree problem?
Thanks.