Although frequent traversal sequence (FTS) mining has been extensively studied over the last decade in web usage mining, it is challenging to extend the mining technique to dynamic web click streams. The main challenge is that existing false-positive methods control memory consumption and output accuracy by a relaxation ratio r (r = e/s, e is the error parameter, and s is the specified minimum support). However, the higher the value of r, the more saving is the memory consumption and the better recall but degrades the output precision, while on the contrary, decreasing r gives a more precise output but needs higher storage space. In this paper, the upper and lower bounds are established to constrain r, a weighted harmonic average (WHA) of the two bounds is designed to adjust r, and a novel algorithm FTS-Stream is proposed to find the FTS over a time-sensitive sliding window. Thus, the precision and recall can be maintained with the WHA (r). Our analysis and experiments show that FTS-Stream has high accuracy and requires less memory in dynamic Web clickstreams.