kingofnumbers's blog

Tree problem
By kingofnumbers, 11 years ago, In English

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.

  • Vote: I like it
  • -8
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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).

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot, I can understand why it's O(n + number of queries + number of integers in output).

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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, fix sp[2]=0; it is a leaf so you add it to the array leaf[0]=2 and add the counter (k=1), and you fix ep[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]].

→ Reply