Could anyone share best resoures to learn trees

Any one share best resources to master trees @cubefreak777

Are you asking for Theory or practice problems ?

@cubefreak777 Both

Assuming that you’re starting from scratch:

  1. Firstly start off by learning about how to represent trees by Adjacency Lists & Matrices
  2. Then Learn about basic searches BFS and DFS. And then spend a significant amount of time in learning how to manipulate these searches specific to the problem at hand, it’s totally pointless to move on to other fancy algorithms unless you’re super strong at this. Solve as many problems as you can to get good as this, you can start solving problems from here. Learn about how find Diameter of a Tree. It should be a quick read.
  3. Now once you feel comfortable enough with bfs and dfs manipultation learn about Binary Lifting you can also check the RMQ Implementation if you’re interested. L
  4. Learn about Tree flattening & Euler tours [Pre-req: Fenwick Trees & Segment Trees].
  5. Now once we’re here you should be able solve almost all problems of CSES Tree Section.
  6. Then learn about DP on trees[Pre-req: Basic DP].
  7. Then study Centroid Decomposition from this cf blog.

Apart from these if you prefer video tutorials then you can go through these videos and mashups by SecondThread and galen_colin.

Algorithms Thread by SecondThread

Mashup Link:
Dashboard - AlgorithmsThread Tree Basics Contest - Codeforces
AlgorithmsThread 8: Tree Basics - YouTube

Topic Stream by galen_colin

Mashup Link:
https://codeforces.com/contests/304970
Topic Stream/Tutorial 3: Trees - YouTube

I might have missed out on some stuff, will update this post whenever I find something worth adding.

10 Likes

Thanks a lot😊 @cubefreak777