# find path from one tree node to another tree node

Discussion in 'Java' started by Peter Mueller, Jan 12, 2008.

1. ### Peter MuellerGuest

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

Peter Mueller, Jan 12, 2008

2. ### Stefan RamGuest

Peter Mueller <> writes:
>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.

Stefan Ram, Jan 12, 2008

3. ### Lars EnderinGuest

Stefan Ram skrev:
> Peter Mueller <> writes:
>> 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.

ITYM shortcut, not abbreviation.

Lars Enderin, Jan 12, 2008
4. ### Peter MuellerGuest

On Jan 12, 3:26 pm, Lars Enderin <> wrote:
> Stefan Ram skrev:
>
> > Peter Mueller <> writes:
> >> 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.

>
> ITYM shortcut, not abbreviation.

Hello Stefan,

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

Peter

Peter Mueller, Jan 12, 2008
5. ### Lasse Reichstein NielsenGuest

-berlin.de (Stefan Ram) writes:

> Peter Mueller <> writes:
>>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
--
Lasse Reichstein Nielsen -
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

Lasse Reichstein Nielsen, Jan 13, 2008
6. ### Stefan RamGuest

Lasse Reichstein Nielsen <> writes:
>>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/.

Stefan Ram, Jan 13, 2008
7. ### Stefan RamGuest

Supersedes: <-berlin.de>

Lasse Reichstein Nielsen <> writes:
>>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 an undirected simple graph,
where any two points can be connected by a unique /simple path/.

Stefan Ram, Jan 13, 2008