Given a rooted tree with N nodes, nodes numbered from 1 to N node 1 is the root
you have to answer queries , in each query you are given a node in this tree and you should output all id's of all leafs in this node's subtree, each query in one line
example:
1
/|\
2 4 3
/ \
5 6
/
7
queries:
1
5
4
2
output:
2 3 6 7
7
6 7
2
expected time complexity O(N + number of queries + number of integers in output)
expected memory complexity O(N)
thanks for helping me.
For each node which has only one child find (and save link to) nearest node in subtree which has more than one child. If some nodes doesn't have such node in subtree save a link to the leaf (there is only one leaf in such subtree). You can do it in O(n).
Now for each query just use a simple dfs. If current node doesn't have childs — output it. If it has only one child — go by saved link. If it has more than one child — go to each of them.
It's not hard to understand why it would be O(n + number of queries + number of integers in output).
Thanks a lot, I can understand why it's O(n + number of queries + number of integers in output).
You can also solve it using DFS. Doing DFS, you add leaves you encounter into an array leaf[]. And when you enter a node, you fix the starting point of that node in the array, and when you leave the node, you fix the end point, so that the leaves of node i will be from the sp[i] to the ep[i] of the array leaf[]. In this example when you enter the node 1, you fix
sp[1]=0;because you hadn't found a leaf yet, then you go to node 2, fixsp[2]=0;it is a leaf so you add it to the arrayleaf[0]=2and add the counter (k=1), and you fixep[2]=k-1;because you get out of the node 2. now if you query node 2 you should print leaf[sp[2]...ep[2]].Nice idea, thanks