What do expect such a storage to provide ? If you just want to encode a rooted tree I am pretty sure storing the parent of every node other than the root is the most efficient way.

I came up with this approach for a tree. We can have 3 arrays. The first array will be about storing the indegree. So initially we will store the indegree of every node. Now we will calculate the prefix sum of this array. Once we have calculated the prefix sum, we will know for every node, how many other vertices it is connected to. Also we can use this array for filling another array with its connected nodes. For example if the indegree of a node is $$$3$$$ and its prefix sum is $$$15$$$ , this means its connected edges will be stored at positions $$$15,14,13$$$ in the second array. Now about the third array we will use it for efficiently filling the second array.

A sample implementation

Probably what you’ve heard was representing graphs using (statically allocated) linked lists. You need 3 arrays:

• $$$vertex[i]$$$ is the neighbouring vertex $$$v_i$$$ of directed arc $$$e_i = (u_i, v_i)$$$ ($$$O(M)$$$ size)
• $$$nxt[i]$$$ is the next arc after $$$e_i = (u_i, v_i)$$$ in the adjacency list of $$$u_i$$$ ($$$O(M)$$$ size)
• $$$head[i]$$$ is the index of the first arc in the adjacency list of $$$i$$$ ($$$O(N)$$$ size)

To ‘add’ an arc $$$(u_i, v_i)$$$ you do sth like:

vertex[i] = v_i
nxt[i] = head[u_i]
head[u_i] = i