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

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?

• There is finding a solution someone else describes, and there is finding a solution on one's own. Given two nodes in the same (rooted (what if not?)) tree, they have common ancestors, which include the root. There is one path between a node and any of its ancestors. There is a "lowest" node that is an ancestor of both. Jan 2 at 6:10
• I suggest you list what operations you want to be able to perform on the tree. You say "easier to locate", but it's not clear exactly how you want to locate them (i.e., what exactly the location operation is). Can you edit the question to make it clearer what you are asking? Your first paragraph talks about indexing; the third paragraph asks about finding the shortest path between two nodes; and those seem like two separate questions. Can you pick one question, and ask about that? If you have two questions, you can post them separately.
– D.W.
Jan 3 at 0:23
• @D.W. I edited my question.
– gil
Jan 3 at 4:49

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.

• The part I do understand (that we work from both vertices, rather than just one), I think is brilliant. What I don't quite understand is when you say the "hash of the index" of a vertex, by "index" do you mean something corresponding to the path of the vertex back to the root, like what you described in the first paragraph? (I think that's what you meant, but in that case aren't depths almost equivalent to indices, in fact just the lengths of indices?)
– gil
Jan 3 at 5:21
• By index I mean the ID of a vertex, or its address in memory. It can be completely arbitrary. The indices of different vertices need to be distinct. Jan 3 at 7:26
• Okay now I get it (mental glitch on my part; I somehow thought the indices must themselves have an ordering corresponding to depth). Very much appreciated.
– gil
Jan 3 at 15:30

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.

• Thanks! I sort of understood that finding the least common ancestor (which I called the "last" common ancestor, probably betraying my background in biology) was the nature of the problem. I didn't know that was exactly the search term to use! (Edit: oh well, I used the term "last common ancestor" in the draft but not in the actual post.)
– gil
Jan 3 at 4:55