Do AIs based on MCTS start each game from scratch?
Your intuition is right. The tree is grown after each game. 

Before the first play through, the values of each decision point are initialized (randomly or to some constant). Then at the end of one play through, the weights of the decision points are updated using Monte Carlo methods. In this way, on the next play through, the updated weights help the agent make a decision in the next game. 

As for how the decision points are added to the tree, it depends on the application. For simple games like TicTacToe, we know all of the decision points. For big games, there are methods to trim the tree of bad performing branches.