## Tree - Connected acyclic graph - Representation

Question

From wiki,

a tree is an undirected graph in which any two vertices are connected by exactly one

Path.

*Path* is connected sequence of edges

# Tree - Example:

It was relatively easy to write multi-walk representation of **rooted** tree,

```
typedef struct multiWalkTreeNode{
struct multiWalkTreeNode * parent;
void *item;
struct multiWalkTreeNode **childPointer;
}Node;
typedef struct multiWalkTree{
Node *root;
int size; /*Number of nodes in the tree*/
}Tree;
```

Question:

In a Tree(non-rooted), there are no children/ancestors to any node

1)

How to represent a Tree(non-rooted)?

2) From maintaining huge size Tree & better `find()`

performance aspect, Do we have multiple representations for a Tree(non-rooted)?

Show source

## Answers ( 2 )

1) Instead of having tracking

`child`

and`parent`

links separately, simply add the`parent`

pointer to`child`

and use`child`

as a complete list of adjacent vertices. From a practical perspective you'll have to maintain a pointer to some vertex as an entry point for`find()`

, but otherwise there won't be anything special about any one node.2) The two most common methods of tree navigation are Depth First Search and Breadth First Search. Generally, Breadth checks if any of the children are the requested node before the recursive calls on the children. Depth checks itself then performs the recursive call on the children until it reaches a leaf. Neither of these are particularly efficient from a memory standpoint, but they're simple enough to write.

You could begin your search of the tree at any of the nodes, and the search time would vary greatly, but I wouldn't call it a different representation of the same tree.

The two basic ways to represent a tree (directed or undirected) are as a

adjacency matrixor as anadjacency list. If it is a "dense" tree (i.e. more than half thenpossible edges for a tree with^{2}nnodes), then it is more efficient to represent it as a matrix. If it is a "sparse" tree (less than half the possiblenedges), then an adjacency list is more efficient.^{2}Your example tree, represented as an

adjacency matrixwould be something like: (please forgive the ASCII art)Each index (horizontally and vertically) corresponds to a node, and a

`1`

is placed in the matrix if the node for that row has an edge to the node for that column, or a`0`

if there is no edge. For example, there is an edge between nodes 3 and 4, so in the matrix, position (3,4) has a`1`

. (Don't forget that in C, of course, array indexes start with 0. I started with 1 because that was the label of the lowest node and this is just an example.)This is a symmetric matrix because it is an undirected graph. You could implement a directed graph by using the row index as the source of the edge, and the column as destination of the edge. Another expansion is to make a

weighteddirected graph by using the value in the matrix as the weight of the edge, instead of just a`1`

.But notice how inefficient this is for your graph. For a graph with

nnodes, you need ann×nmatrix (in terms of space,ntimes the size of storing one value). Most of the spaces are empty (^{2}`0`

) anyway.The other basic method is the

adjacency list, which is just that: a list of the adjacent nodes---a list ofedges. An adjacency list for your graph might be:As long as you know this is an undirected graph, you can get away with only recording 1,4 and just know that this is equivalent to 4,1. For a directed graph, of course, you could say that 1,4 means only "from 1 to 4". Notice that the amount of information you have to store using the adjacency list representation depends on the number of

edges, not the number ofnodesas with the matrix representation.I'll leave it you to figure out how to implement in C a two-dimensional matrix or a list of pairs of values.

Note that both the adjacency matrix and adjacency list only represent the

edgesbetween the nodes. You might also want to store some dataineach node. This would require a separate structure, such as a list or an array.