Technical Interview Questions
Please refer to the list of all data structures to find what you're looking for.
Don't optimize too soon. Start with the simplest approach that meets the requirements. You will have time to optimize once you've solved the problem. And you will find it much easier to focus your attention on the optimization once you've got a working solution. Plus, you'll likely have tests that will ensure that you don't introduce regressions (breaking the original solution) with the optimization. Start small, build a test harness to verify that your solutions does what it needs to do (and what you think it does), and optimize incrementally as you get more familiar with what you've built.
Create a few sample Trees as test cases before you start coding. There are lots of edge cases with Trees that can trip you up if you don't test your solution on a few samples before you start coding.