[humanjas]

Code

1 public int pathlength(Tree t) {
2 return pathlength(t.root(), 0);
3 }

4 private int pathlength(Node v, int depth) {
5 if (v == null) return depth;
6 int result = depth;
7 for (Node c: v.children())
8 result += pathlength(c, depth+1);
9 return result;
10 }

How do you start calculating the space complexity of this through recurrence equations?

I started with the base case, which is a constant 'c1'.

Then they have a recursive call which is 'h' times a constant 'c2'. 'h' is the amount of children of the root.

But how do you continue with this?

Thanks in advance.

[Stealth™]

Are you trying to find the height of the longest path? Or the total number of nodes?

[humanjas]

Already found the answer. I had to calculate the space complexity of this algorithm, using recurrence equations. The answer was O(h), I thought too complicated.