My usual strategy for this is that every parse tree node holds on to the first token of the parse element from which it was constructed, and sometimes the last too. The initial token is definitely available at the point you begin parsing the syntactic element. This lets me identify at least the line and often the span of the syntax element in question; depending on the structure the tokens use I may be able to reconstruct the entire input source. I carry this over to any derived syntax tree nodes, so the token lifetime is the entire run of the program.
For structures where holding on to a reference to a token entity itself is infeasible, simply storing the index of the tokens into the stream is sufficient. You simply retain the token stream itself alongside. At the extreme, even a byte index is good enough if you still have access to the source text and can re-lex it. These values are cheap enough to add to any AST nodes, and definitely available at the time of parsing the tokens. Because errors are relatively rare, the cost of re-lexing (or even re-parsing!) is negligible.
In some cases, it may be cheaper to go in the other direction: if each token only produces to a single syntax tree node, the token can hold a reference to that node, and error reporting can walk the tokens to find the operative node. I'd expect this to be relatively uncommon, but a single-layer parse tree in Rust is one plausible case.
Error messages commonly only identify the line of the error; in this case, each node can also just hold on to the line number of one of the tokens contributing to it, and perhaps a character index, as integers. This is generally good enough for multi-line constructs, though it's not going to produce "good" error messages. This is a cheap option when the source will not be available at run time.
The final option is to have a separate collection of debug symbol information — either an array or dictionary in the runtime, or in a sidecar file — and save any relevant data indexed by a unique identifier for each syntax tree node. You may already have those identifiers, or can (re)construct them easily: even "the third
if node in a pre-order depth-first traversal" is good enough as an identifier when it's for generating an error message, so you don't need to have any additional inline data within the nodes. The debug data can store byte or token indexes, or even the annotated source code itself: a text file of
node identifier|source line pairs could do the job.
For a number of these options, a key aspect is that the token data is only used when reporting an error: this is a slow human-level operation anyway, so even doing extra processing all over again is cheap enough to be satisfactory. You can store the bare minimum information to reconstruct the lexical data for reporting, outside of the core loop of the system. In cases where it's hard to do, there's really no benefit in refactoring to achieve optimal performance for a rare and terminal case.