how do you implement trees

general
,
1

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

2

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.

1 Like
3

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:

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!

2 Likes
4

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

vector V[10000];

Then when you input you push the node to its adjacent node.

e.g.

3 2

1 2 <-

2 3

For the marked input line, you push node 2 to V[1] (and 1 to V[2] 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. :stuck_out_tongue:

1 Like
5

oh thats a great idea…thanks

6

thanks a lot and it would be best if you add some questions thanks again

7

thanks…

8

See the edit…