Is there an structure that allows for a flat representation of trees with constant access to any element?

One can, for example, represent 2d arrays such as:

[[1,2],[3,4],[4,5]]

as flat arrays:

[1,2,3,4,5,6]

as long as he transforms the indices before accessing:

index(x,y) = x + y*2 // because internal width=2

This is often faster. My question is: is it possible to use a similar approach of representing an structure as a flat array, for, instead of n-dimensional tables, free-form trees such as:

[[1,2,3],4,[5,[6,7]],8]

Well, it depends a bit on the operations. You cannot do anything reasonable if you want to realize you data structure inside an $n$-elementary array. The 2d array works, since there is a bijection between the 2d array entries and the 1d array entries. There is also such a bijection for any fixed tree, but I think this is not what you are looking for.

Notice that your tree decoding [[1,2,3],4,[5,[6,7]],8] also uses more structure than a normal 1d array. So if you ask for data structures of size $O(n)$ with $O(1)$ operations than you can actually do something.

One idea is to use a array where you store the DFS-tour (sometimes called Euler tour) of your tree, and the information about the time when you discover and when you finished a vertex in the DFS search. This can be stored inside an array of size $4n$ plus another $n$ for the values at the nodes, and it allows you to navigate through the tree using $O(1)$ operations per step.

With more involved data structures you can also answer level ancestor queries (what is the $i$-th vertex about vertex $x$?) or lowest common ancestor queries in constant time with a data structure of size $O(n)$. If you want to know more about these two data structures, look up the references in wikipedia.

StackExchange Computer Science Q#18247, answer score: 3