Need help with Trees...(8-puzzle)

I have an assignment that needs to be done in a little more than 2 weeks, and it is based on understanding of the Trees implementation in Java. I am to create an 8-puzzle game, where it is possible to push a button and solve the puzzle. I have been reading much about the trees structure and function, but I do not get the standard idea of how to create a tree at all. Is there a blueprint a beginner can follow to make a simple tree with for example 3 nodes? It would be of great help if anyone could pinpoint me of on how to create a small tree, just to start with.

Just for the record, I have been notified by my teacher that the correct method of doing this would be adding nodes as I am searching through the tree for the solution. Is this correct? What I don't get is how my code can search through something that not yet is created... so I get confused :(

Any help is greatly appreciated. Thanks in advance.