How to index a tree to allow efficient search for paths?

Question

By "indexing" I mean assigning addresses or labels or whatever to nodes to make them easier to locate, similar (in its effect, not necessarily in the implementation) to how a database can be indexed.

I feel this question must be pretty elementary, but as a CS noob I don't know how to search for the answer. I may not even be phrasing the question correctly.

So let me describe a hypothetical use case. Say my program stores a chess game (including variations) as a tree, with each node representing the state of the game after a move. Given any two nodes which are guaranteed to be in the tree, what is the most efficient way to find the path (a sequence of intervening nodes) from one to the other? I'm mostly concerned with time complexity, although I'd like to save space as well (not sure how to express myself more precisely).

Edit: to clarify what I want, say I have a Python program like this:

tree = Tree(game_record)  # there's a tree constructed from a game record

# this tree can be traversed by calling `advance` and `backtrack`
tree.advance(child=0)  # advance the game into the first child of the current node
tree.backtrack()  # backtrack to the parent of the current node

# and it can tell you which node it's currently at
current_node = tree.current_node()

# now this is my question: at first we're at one node
node1 = tree.current_node()
# after some advancing and backtracking, we arrive at another
node2 = tree.current_node()
# I want a method that returns the path from node1 to node2
tree.find_path(node1, node2)  # should return something like [node3, node4, ...]

# what would be a good way to implement this method?

Walking the whole tree is probably not it. I'm thinking that maybe each node can be assigned an informative address, perhaps an array. One scheme would be to let a child's address be one element longer than its parent's, where the extra element uniquely identifies the child. So if the first node has address [0], its children would have [0, 0], [0, 1], ... and the children of [0, 1] would have addresses like [0, 1, 0], [0, 1, 1], and so on. With this scheme the nodes on the path between any two nodes can be directly read off from their addresses.

With a tall tree though, the addresses can get quite long. Not a real concern for a chess program, but this way of indexing a tree just feels inefficient and inelegant to me. Is there a better way to assign addresses? Or is there a completely different approach to this problem?

Answer 1

Root the tree in an arbitrary fashion. Given two nodes $x,y$, let $x_0 = x, x_1, \ldots$ and $y_0 = y, y_1, \ldots$ be the paths going up the tree all the way to the root. If $x_i = y_j$ then the unique path between $x$ and $y$ is $x_0,\ldots,x_i=y_j,\ldots,y_0$.

In order to find this path quickly (at the cost of a little bit of memory), generate the two paths in parallel, $x_0,y_0,x_1,y_1,x_2,y_2,\ldots$, storing the resulting vertices in a hash table, until they collide. This happens at time $\max(i,j)$, which is the same as the path length $i+j$ up to constant factors.

---

While the description above suggests that you have to store the entire tree ahead of time, this is not necessarily the case. In general, all you need to do is to have a consistent way of determining which of the neighbors of a given vertex is its parent. Whether this is possible without storing the entire tree depends on the problem. When it is possible, you can generate the tree "as you go", which prompts us to reduce the space complexity of the algorithm (perhaps you don't need to store the path from $x$ to $y$, but only to generate it vertex by vertex).

---

If space is at premium, you can save a factor of $k$ by storing only a $k$'th fraction of the vertices. Say that a vertex is ($k$-)special if the hash of its index is divisible by $k$. Perform the search as above, but only store special vertices. On average, this will cut the number of vertices stored by a factor of $k$. However, it doesn't give you the exact intersection point. Suppose that your sequences contain the special points $x_{i_1},\ldots,x_{i_a}$ and $y_{j_1},\ldots,y_{j_b}$, where $x_{i_a} = x_{j_b}$. To find the exact intersection point, it suffices to consider the small parts $x_{i_{a-1}+1},\ldots,x_{i_a}$ and $y_{j_{b-1}+1},\ldots,y_{j_b}$.

If space is still at premium, you can use exponential search followed by binary search. We go over $k=1,2,4,8,\ldots$, and for each value of $k$, determine only the first $k$-special vertex after the initial vertices $x,y$. Suppose that for some $k$, these special vertices coincide. Now generate the sequence of $k/2$-special vertices, until they coincide. Let $x_{i_a}=y_{j_b}$ be the first time these sequences coincide. Then we can narrow the search down to $x_{i_{a-1}+1},\ldots,x_{i_a}$ and $y_{j_{b-1}+1},\ldots,y_{j_b}$. Now we generate the sequence of $k/4$-special vertices, starting at $x_{i_{a-1}+1},y_{j_{b-1}+1}$ (unless these vertices are the same, in which case we are done); and so on. The running time is still linear, but the space requirements is down nearly to a constant (in expectation).

We can get the space down to a deterministic constant by defining special in terms of the depth of a vertex rather than in terms of its index, but depth is not necessarily easy to compute.

Answer 2

Given a tree, you can preprocess it (attaching extra information to each node) so that you can answer least common ancestor queries. A least common ancestor query is this: given two nodes $u,v$, find the lowest node $w$ that is a parent of both of them. Finding the path between two nodes can be reduced to a least common ancestor query: if the least common ancestor of $u,v$ is $w$, then the path from $u$ to $v$ involves going up from $u$ to $w$, then down from $w$ to $v$.

Yuval Filmus's answer may be more useful in practice, but I thought I'd share this connection to a standard data structure in case it is helpful.