hello @all,how do you all implement tree data structure when you see a problem related to it.I mean to say do you make structure and pointers to left and right child like we see in websites and books or there is any other way(any stl) way to implement…because in competions its difficult to deal with so many pointers and links
Yes, usually, we implement it on our own. This also gives us the added benefit of tweaking each node to have any bookkeeping or any “super-power.”
What I would suggest you, is to make a correct skeleton program for trees, and keep the source code easily accessible. Next time you see a question, you can re-use this code, with any modifications/tweaks as required, if any is needed.
Usually there are less questions I suppose in which we actually need to implement the tree. I don’t think I ever needed. Questions are such that they can be solved by using just the basic concept of it.
See these two questions I remember:
- You may like seeing this: http://www.codeproject.com/Articles/602805/Creating-a-Binary-Search-Tree-B
In rest questions I believe, its more of the concepts of trees and graphs mixed. Usually traversals(bfs and dfs) are needed for which vectors are most common. Some spoj questions are there, I’ll add them asap!
- http://www.spoj.com/problems/PT07Y/ (This is on codechef too, but test cases on codechef are very weak, you can read comments on codechef for this question)
You can implement tree the same way any graph is done. Use array of vectors to store adjacent nodes of every node.
For example take this problem.
Here we have to input a tree of max number of nodes 10000.
So we declare an integer vector as
Then when you input you push the node to its adjacent node.
1 2 <-
For the marked input line, you push node 2 to V (and 1 to V for undirected graph). Do this for every edge and you have a graph for the given tree. Then you can use any algorithm e.g. DFS/BFS you wish. Now, how to solve this problem is a different issue.
oh thats a great idea…thanks
thanks a lot and it would be best if you add some questions thanks again
See the edit…