Trees

Question

In GATE if questions just mention a tree then should we assume it to be a directed or undirected tree?

Also, if we are having an undirected tree then does the child node contains a pointer to the parent node?

Comments

Ideally, most of the relevant information should be mentioned in the question and it should be applicable for all the exams because it minimizes the ambiguity and assumptions.

Let alone directed or undirected, definition of tree and degree should be mentioned in the question because definitions of tree and degree also vary . Some authors consider tree as “rooted tree” and number of subtrees of a node is called the degree of that node and some authors defined it as number of incident edges on a node. But I have hardly seen the definition of tree and degree in GATE questions.   

If it is not mentioned whether tree is undirected or directed, you should go with undirected because most of the books and previous year questions consider graph as undirected graph and if they meant directed graph then they should specify. In worst case, you can claim it that it is not mentioned that graph is directed or undirected, so I have assumed an undirected graph.

The second thing you have asked is related to “tree representation” or more specifically, how to represent tree in computer (defined as memory representation of the tree). You are having two links LLINK() and RLINK() within each node and there is a link variable T which is a pointer to the tree. LLINK(T) and RLINK(T) are pointers to the left and right subtrees of the root, respectively. And, these rules are defined recursively. So, child node is not having a pointer to the parent node otherwise it is having a loop which a tree does not have.

Answer 1

In math, yes, assume undirected tree. In Computer Science, assume directed tree.

Comments

Any reference for this?