Tree testing is designed to give you rough answers early in the design process:

• Initial research
  Along with the other up-front research you would normally do (surveys, interviews, card sorting, and so on), it’s useful to doing a baseline tree test of the existing site. This shows you problem areas to investigate, and provides a benchmark score that you can compare your new site structure to.
  
  
• Early design phase
  It’s common to start drafting your site structure while doing the first conceptual round of interaction design. As soon as you have one or two tree ideas roughed out, you can run tree tests to see how well they work (compared to each other and the existing structure), and what needs to change.
  
  
• NOT late in the project
  Once you have a working prototype or a real site constructed, it’s better to do traditional usability testing because it combines everything that affects your IA - not just organisation and labelling, but also navigation, page design, visual design, and content.

Next: How long will it take?