find path from one tree node to another tree node

[Peter Mueller]

Hello,

I have a non binary tree and looking for a solution to find the path
between two given nodes (not just leaves).
Is there a class in the Java class library that provides the
functionality already? If not, can someone
recommend a library. A description of the algorithm would also help.

Thanks,
Peter

 

[Stefan Ram]

I have a non binary tree and looking for a solution to find the path
between two given ¯¯¯¯¯¯¯¯

Sometimes, there are /several/ paths between two points. But
you surely can go up to the root and then down to the other
point. (The last path can be constructed by going up to the
root from that other point.)

If you find another common ancester by this, you even can take
an abbreviation.

However, there will not be any path if the tree is empty.

 

[Lars Enderin]

Stefan Ram skrev:

Sometimes, there are /several/ paths between two points. But
you surely can go up to the root and then down to the other
point. (The last path can be constructed by going up to the
root from that other point.)

If you find another common ancester by this, you even can take
an abbreviation.

ITYM shortcut, not abbreviation.

 

[Peter Mueller]

Stefan Ram skrev:




ITYM shortcut, not abbreviation.

Hello Stefan,

I wrote a tree class realizing this method. Works fine for me.
Thank for the hint.

Peter

 

[Lasse Reichstein Nielsen]

Sometimes, there are /several/ paths between two points.

Not in a tree. Unless you allow going back and forth along the
same edge as part of a path (i.e., visiting the same node
twice), there is exactly one path between any two node.

However, there will not be any path if the tree is empty.

Nor will there be any nodes, and since the question was on how
to find a path between two nodes, we know the tree isn't empty.

Apart from that, the solution is fine. Trace a path from each node
to the root. Then find the lowest node that is on both paths and
make a path from one node to that node, and from there to the other node.

If your tree keeps information about the depth of each node in the node,
then you won't have to trace the paths all the way to the root, but can
compare nodes at the same lavel until the paths meet.

/L

 

[Stefan Ram]

Not in a tree. Unless you allow going back and forth along the
same edge as part of a path (i.e., visiting the same node
twice), there is exactly one path between any two node.

This indeed is allowed for a path - otherwise it would be a
called a »simple path«. (Sometimes »simple« might be omitted,
when it can be deduced from the context. This might have been
possible in the case of the OP.)

A tree, then can be /defined/ as a graph, where any two points
can be connected by a unique /simple path/.

 

[Stefan Ram]

Supersedes: <[email protected]>

Not in a tree. Unless you allow going back and forth along the
same edge as part of a path (i.e., visiting the same node
twice), there is exactly one path between any two node.

This indeed is allowed for a path - otherwise it would be a
called a »simple path«. (Sometimes »simple« might be omitted,
when it can be deduced from the context. This might have been
possible in the case of the OP.)

A tree, then can be /defined/ as an undirected simple graph,
where any two points can be connected by a unique /simple path/.