Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 FindPathBetweenTreePositions

Source Notebook

Return the path linking two tree nodes specified by their positions

Contributed by: Shenghui Yang

ResourceFunction["FindPathBetweenTreePositions"][start,end]

returns a path on that connects the start and end point given their positions on a tree.

Details

The tree positions start and end support the specifications returned by TreePosition. Each position {i1,i2,…,ik} specifies the path from the root to the node by giving the index of the child chosen at each level. For example, {2,1} means "the first child of the second child of the root."
ResourceFunction["FindPathBetweenTreePositions"] is based on the lowest common ancestor using the resource function LongestCommonPrefix.
A Tree object can have duplicated values but all positions of the nodes are unique.
The path between positions is independent of the Tree and does not require a Tree as an input.
ResourceFunction["FindPathBetweenTreePositions"] returns $Failed if the given position is not a valid tree position.

Examples

Basic Examples (2) 

Find a path between two tree positions:

In[1]:=
ResourceFunction["FindPathBetweenTreePositions"][{2, 1}, {1, 2, 3}]
Out[1]=

Create a tree:

In[2]:=
SeedRandom["Tree5"]; myTree = RandomTree[40]
Out[3]=

Find the path that connects the given nodes labeled 24 and 21:

In[4]:=
{start, end} = First /@ Comap[{TreePosition[24], TreePosition[21]}, myTree]
Out[4]=
In[5]:=
ResourceFunction["FindPathBetweenTreePositions"][start, end]
Out[5]=

Scope (1) 

Visualize the path that connects the given nodes labeled 63 and 82 on the given tree:

In[6]:=
SeedRandom["Tree5"]; myTree = RandomTree[90, ImageSize -> 360]; startAndEnd = First /@ Comap[{TreePosition[63], TreePosition[82]}, myTree]
Out[8]=
In[9]:=
pth = ResourceFunction[ "FindPathBetweenTreePositions"] @@ (startAndEnd); Tree[myTree, TreeElementStyle -> (# -> StandardBlue & /@ pth)]
Out[10]=

Properties and Relations (2) 

If one of the starting point or ending point is {}, then the path always starts or ends at the root node:

In[11]:=
SeedRandom["Tree5"]; myTree = RandomTree[40, ImageSize -> 300]; pth1 = ResourceFunction[ "FindPathBetweenTreePositions"][{}, {2, 7, 1, 1, 2, 2}]
Out[13]=
In[14]:=
Tree[myTree, TreeElementStyle -> MapIndexed[# -> Lighter@ColorData["BlueGreenYellow"][#2[[1]]/7] &, pth1]]
Out[14]=
In[15]:=
pth2 = ResourceFunction[ "FindPathBetweenTreePositions"][{2, 7, 1, 1, 2, 2}, {}]
Out[15]=
In[16]:=
Tree[myTree, TreeElementStyle -> MapIndexed[# -> Lighter@ColorData["BlueGreenYellow"][#2[[1]]/7] &, pth2]]
Out[16]=

If the starting point and ending point are identical, then the path is the list of single element if it is valid:

In[17]:=
SeedRandom["Tree5"]; myTree = RandomTree[40, ImageSize -> 300]; pth = ResourceFunction[ "FindPathBetweenTreePositions"][{2, 7, 1, 1, 2, 2}, {2, 7, 1, 1, 2, 2}]
Out[18]=
In[19]:=
Tree[myTree, TreeElementStyle -> (# -> StandardBlue & /@ pth)]
Out[19]=

Possible Issues (1) 

If any element of the given positions is not a positive integer, the function returns $Failed:

In[20]:=
ResourceFunction[ "FindPathBetweenTreePositions"][{2, -100, 1, 1, 1}, {2, 7, 1, 1, 2, 2}]
Out[20]=

Neat Examples (2) 

Find all nodes in the tree that are 8 steps away from the node 33 (all values are distinct):

In[21]:=
SeedRandom[12345]; myTree = RandomTree[80, ImageSize -> 360]; Tree[myTree, TreeElementStyle -> {(TreePosition[myTree, 33][[1]]) -> Orange}]
Out[23]=

Obtain a list of all positions on tree and all paths starting from node with value 33:

In[24]:=
posList = Reap[TreeScan[Sow, myTree, All -> {"Position"}]][[2, 1]]; With[{node = TreePosition[myTree, 33][[1]]}, paths = ResourceFunction["FindPathBetweenTreePositions"][node, #] & /@ Complement[posList, node]; Map[TreeExtract[myTree, #, TreeData] &, paths, {2}] /. {} -> TreeData[myTree] ] // Short
Out[25]=

The distribution of the distances between node 33 and other nodes on the tree:

In[26]:=
Histogram[Length /@ paths]
Out[26]=
In[27]:=
candidates = Select[paths, Length[#] == 8 + 1 &]; Grid[Partition[Table[ Tree[myTree, TreeElementStyle -> (# -> StandardBlue & /@ p), ImageSize -> 360], {p, candidates}], 4], Dividers -> All]
Out[28]=

A histogram that resembles Half Dome (a mountain in Yosemite):

In[29]:=
SeedRandom["Tree2"]; myTree = RandomTree[199]
Out[30]=

Compute pair-wise distance for all nodes and plot their frequency with Histogram:

In[31]:=
Once[LaunchKernels[]]; pos = Reap[TreeScan[Sow, myTree, All -> {"Position"}]][[2, 1]]; pairs = Subsets[pos, {2}]; Histogram[ Length /@ Parallelize[ ResourceFunction["FindPathBetweenTreePositions"] @@@ pairs]]
Out[34]=

Compare with the actual mountain:

In[35]:=
ImageReflect[ First@WebImageSearch["Half Dome Mountain", MaxItems -> 1], Left]
Out[35]=

Publisher

Shenghui Yang

Version History

  • 1.0.0 – 24 September 2025

Source Metadata

Related Resources

Author Notes

Tree object can have duplicated values but all positions of the nodes are unique.

License Information