Tree Traversal - Find between two leaves

Question

I have a network node map, and I need to build a list of nodes between two points. It sounded simple enough to me at first, but the answer is eluding me :(

Given the (simplified) data structure of:

Id    Name        LeftId  RightId
1     Skagway     3
2     Klukwan     3
3     Haines      2       4
4     Juneau      3       5
5     Petersburg  4       6
6     Wrangell    5       7
7     Kasaan      6       4
8     Portage     4       6

How do I build an algorithm (or can you suggest an algorithm) to build a traverse the nodes and build a list of all the nodes between two points? The tree is mostly linear, except in the few spots where its not.

They would like to be able to identify the nodes starting from either the branch or leaf end.

Answer 1

If it is a path from one node to another, I suggest you using preorder on the subtree with a root node of the starting node you want the path to log from. UPDATE: In fact, artificial intelligence algorithms (and searching paths in graphs) may also be of use. For example, the very simple one, BFS could be of use.