an algorithm - suffix tree

Question

Given a generalized suffix tree of 2 strings : st1 and st2.

Need to find an algorithm that marks every node V in 1 (and/or 2) if there is a leaf in the sub-tree that goes out of V that represents suffix of st1 (and/ or st2 respectively).

my guess is that we need to use the fact that the last letter of every suffix of st1 is $ and the last letter of every suffix st2 could be #. but it seems to me inefficient to scan tree from bottom to top.

any ideas how to approach it?

for example: I have two strings: st1=abab , st2=aab. in the picture I have made the generalized suffix tree with the marks. so from node with the letter a I have a leaf from his sub tree that represents suffix of st1 so I marked it 1, and I have a leaf from his sub tree that represents suffix of st2 so I marked it 2 as well.

Answer 1

When you do DFS, you can mark parent node (after visiting children) with flag for '1' and/or '2', depending if you have end mark for st1/st2 or child is already marked as sufix for st1/st2.

This takes advantage of fact that if any of children contains sufix for st1, then parent also has to contain sufix of st1.