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. My question is, 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).
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?