First - yes that's in all the sutra traditions. The sutras talk about how when Buddha  on the night he became enlightened, in the first watch:

"When the mind was thus concentrated, purified, bright, unblemished, rid of defilement, pliant, malleable, steady, & attained to imperturbability, I directed it to the knowledge of recollecting my past lives. I recollected my manifold past lives, i.e., one birth, two... five, ten... fifty, a hundred, a thousand, a hundred thousand, many eons of cosmic contraction, many eons of cosmic expansion, many eons of cosmic contraction & expansion: 'There I had such a name, belonged to such a clan, had such an appearance. Such was my food, such my experience of pleasure & pain, such the end of my life. Passing away from that state, I re-arose there. There too I had such a name, belonged to such a clan, had such an appearance. Such was my food, such my experience of pleasure & pain, such the end of my life. Passing away from that state, I re-arose here.' Thus I remembered my manifold past lives in their modes & details.

"This was the first knowledge I attained in the first watch of the night. Ignorance was destroyed; knowledge arose; darkness was destroyed; light arose — as happens in one who is heedful, ardent, & resolute. But the pleasant feeling that arose in this way did not invade my mind or remain.

Readings from the Pali Canon

That's in the sutras for sure. That's in the Pali canon, so from the earliest Therevadhan tradition.

So anyway - I read that as the barriers between past, present and future falling away. Not seeing time in such a linear way as we do. That the past is in some way here in the present and the present in the past and the future also in both and that at the moment when he became enlightened, he had deep insight into this. So it's not just the past and present, but how they relate to each other, how the present arose from the past. So whatever it was, much more than just a memory as we think of it.

I think that's a Mahayana way of looking at it though, as I have learnt about Buddhism mainly within the Tibetan traditions. So not sure how the Thervadhans think about it.

It's a good question! I know I haven't really answered it, just given perhaps a sidelight on it. I know that the topic of how actions and their consequences are passed through from past to present has been discussed a lot with many different schools of opinion there from scholars. And expect the same for this idea of memory of past lives.

Usually you have no memory at all of previous lives. Reincarnate Lamas - again not expected to remember their previous lives like the Buddha. And he warned his followers against trying to find out who they were in previous lives.

But as you say, the sutras say he remembered his own past lives .Also gave stories of his lives.

Buddha actually taught that the precise workings out of the laws of Karma is one of the four imponderables. It's one of the things that you can't sort out by reasoning about them and it is a distraction from the path to try to understand how it works exactly.

He says of one of the other four imponderables, the nature of the Buddha, that it is a bit like asking, when a fire is out, which way it went, whether east, or west or south or north.

This is the wikipedia article about it: Acinteyya

And this is from the old article about Karma in Buddhism. You can tell from this how karma is thought of in Buddhism, and I think the same would be said for the Buddha's understanding of his past lives.

"In the Buddhist view, the relationship between a single action and its results is dependent upon many causes and conditions, and it is not possible for an ordinary being to accurately predict when and how the results for a single action will manifest. Ringu Tulku Rinpoche states:

"Sometimes, in order to help us understand how particular actions contribute to particular kinds of result, such as how good actions bring about good results and how bad actions bring about bad results, the Buddha told stories like those we find in the Jataka tales. But things do not happen just because of one particular cause. We do not experience one result for every one thing that we do. Rather, the whole thing—the entire totality of our experience and actions—has an impact on what we become from one moment to the next. Therefore karma is not just what we did in our last life, it is what we have done in this life too, and what we did in all our lives in the past. Everything from the past has made us what we are now—including what we did this morning. Strictly speaking, therefore, from a Buddhist point of view, you cannot say that there is anything in our ordinary experience that is not somehow a result of our karma."

Bhikkhu Thanissaro explains:

"Unlike the theory of linear causality — which led the Vedists and Jains to see the relationship between an act and its result as predictable and tit-for-tat — the principle of this/that conditionality makes that relationship inherently complex. The results of kamma experienced at any one point in time come not only from past kamma, but also from present kamma. This means that, although there are general patterns relating habitual acts to corresponding results [MN 135], there is no set one-for-one, tit-for-tat, relationship between a particular action and its results. Instead, the results are determined by the context of the act, both in terms of actions that preceded or followed it [MN 136] and in terms one’s state of mind at the time of acting or experiencing the result [AN 3:99]. [...] The feedback loops inherent in this/that conditionality mean that the working out of any particular cause-effect relationship can be very complex indeed. This explains why the Buddha says in AN 4:77 that the results of kamma are imponderable. Only a person who has developed the mental range of a Buddha—another imponderable itself—would be able to trace the intricacies of the kammic network. The basic premise of kamma is simple—that skillful intentions lead to favorable results, and unskillful ones to unfavorable results—but the process by which those results work themselves out is so intricate that it cannot be fully mapped. We can compare this with the Mandelbrot set, a mathematical set generated by a simple equation, but whose graph is so complex that it will probably never be completely explored."

Karma in Buddhism (the article as it was up until autumn 2014 - this section was removed from it shortly after)

It's also related to the sixteen unwise reflections, which we tend to spend so much of our time entangled with:

What am I?

How am I?

Am I?

Am I not?

Did I exist in the past?

Did I not exist in the past?

What was I in the past?

How was I in the past?

Having been what, did I become what in the past?

Shall I exist in future?

Shall I not exist in future?

What shall I be in future?

How shall I be in future?

Having been what, shall I become what in future?

Whence came this person?

Whither will he go?

The Buddha states that it is unwise to be attached to both views of having and perceiving a self and views about not having a self. Any view which sees the self as "permanent, stable, everlasting, unchanging, remaining the same for ever and ever" is "becoming enmeshed in views, a jungle of views, a wilderness of views; scuffling in views, the agitation (struggle) of views, the fetter of views."

See The unanswered questions - Sabavassa Sutta

Note, the current version of the Four Noble Truths in wikipedia is also really poor. It doesn't even list the four truths in the lede, which is also very short. Before it had a list of the four truths, but rewritten with many mistakes.

The original version is here: Four Noble Truths

I and another editor tried for ages to get these two articles reverted but no success. (I got involved as a reader of these articles rather than a contributoer - the other editor was one of the contributors).

The new versions are supposedly simplified to make them easier for a modern reader to read, but in the process then they lose the essential teachings.

For instance the aim of the Buddhist path is not to just try to cease to exist as the current articles on the four noble truths and Nirvana suggest.

Cessation is the cessation of suffering, and its causes, not the cessation of the individual - which on realizing Nirvana you realize never existed in the first place in the sense you thought it was there, so there was nothing to cease existing.

You might also like my occasional blog posts about Buddhism: Some ideas about Buddhist teachings