find path from one tree node to another tree node

Thread view:

Peter Mueller - 12 Jan 2008 09:34 GMT

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

Reply to this Message

Stefan Ram - 12 Jan 2008 14:09 GMT

>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.

Reply to this Message

Lars Enderin - 12 Jan 2008 14:26 GMT

Stefan Ram skrev:

>> I have a non binary tree and looking for a solution to find the path
>> between two given ¯¯¯¯¯¯¯¯
[quoted text clipped - 6 lines]
> If you find another common ancester by this, you even can take
> an abbreviation.

ITYM shortcut, not abbreviation.

Reply to this Message

Peter Mueller - 12 Jan 2008 18:22 GMT

> Stefan Ram skrev:
>
[quoted text clipped - 10 lines]
>
> ITYM shortcut, not abbreviation.

Hello Stefan,

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

Peter

Reply to this Message

Lasse Reichstein Nielsen - 13 Jan 2008 02:18 GMT

>>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.

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

Signature

Lasse Reichstein Nielsen - lrn@hotpop.com
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

Reply to this Message

Stefan Ram - 13 Jan 2008 02:25 GMT

>>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.

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/.

Reply to this Message

Stefan Ram - 13 Jan 2008 02:36 GMT

Supersedes: <path-20080113032202@ram.dialup.fu-berlin.de>

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/.

Reply to this Message

find path from one tree node to another tree node

Free Magazines