CareerCup

1. You can do this in O(n^2) without using extra space.
2. Use O(n) extra space and solve it in O(n).

If we had parent pointers, we could do a BFS starting at given node, treating parent and child pointers as undirected edges.

if parent pointer not given , do bfs to find start node and corresponding path from root to start,
then traverese this path backwards, decrementing k
j = k--
k = j # use of j is not required ,its just to explain
and recurse on its children other than child which was previous node on path i.e recurse( child, j-1) # note that j is further decremented