Following on from Michael's answer, if you are logically deducing from 'must have bought' - you have a situation where you are deducing from the fact that there is a notebook there, that you must have bought it (and didn't remember buying it!). That's not incorrect, but it is very very unlikely.
The second version is more likely, but I think that most people would say 'Before I could take the bus to school, I had to buy a new notebook', as going to school is conditional on getting the notebook.