There are a number of crates that encode tree structures in a Vec such as id_tree. In simplest case they build tree structure by pointing to other indices in the Vec for things like parent and children references.

Are there any crates that encode tree in Vec by just storing a depth along with each item in the Vec?

In fact, the set of integer sequence d of length n such that

d[i] >= 0 for all 0 <= i < n,

d[0] = 0

d[i+1] - d[i] <= 1 for all 0 <= i < n-1

precisely represents the set of preordered depth sequence of trees of n nodes.

The balanced parenthesis (BP) representation of a tree is used in succinct data structures because it can be used to store a tree of n nodes in 2n bits and it is asymptotically optimal.

Storing depths can be considered as an implementation of BP representation, I think. However, depth information is usually stored with a BP representation in more space-efficient ways.

For example, by only storing depths per 64 positions, the depth of a node at position i can be computed by something like: depth[i / 64] + i % 64 - (bp[i / 64] & ((1 << i % 64) - 1)).count_zeros() * 2 where bp is the bit-vector of the parentheses. This is the naive form of the rank-dictionary structure.

This library breaks text into left-to-right and right-to-left text runs. These text runs can be nested within each other (for example, an English sentence might contain a quote in Hebrew, which in turn contains a name in Vietnamese), so they naturally form a tree structure. The Unicode Bidirectional Algorithm encodes this tree structure as a sequence of â€śembedding levels,â€ť which correspond to the depth of the tree at each point in the string.

You might also be interested in using a heap, if it suits your use case. It is a partially ordered data structure represented by a full binary tree usually in flat array form, so the index of a node implicitly encodes its depth.