Recursive tree search to get the node level

Question

I have a dataset that contains a tree similar to the tree below.

  son father
1   1     NA
2   2      1
3   3      1
4   4      2
5   5     NA
6   6      2
7   7      4
8   8      5
9   9      4

Built a function that allows me to search the entire hierarchy of a node (son)

getTree = function(sons){
   if( length(sons) > 0 ){
      sons = subset(df, father %in% sons)[['son']]
      sons = c(sons, getTree( sons ))
   }

   return(sons)
}

subset(df, son %in% getTree(8))

That returns me

  son father
4   4      2
6   6      2
7   7      4
9   9      4

However, in addition to the hierarchy, it is necessary to know at which level of the tree that node (child) is. How do I change, or create another function that allows me to achieve this?

Thanks in advance!

Answer 1

I'm not sure exactly what your function is meant to find in the tree, but here's an example in Python that finds the deepest children nodes in the table along with the depth. It uses a incremented counter on each call that keeps track of the depth:

In [140]: def traverse(sons, depth=0):
     ...:     next_sons = sons[sons['father'].isin(sons['son'])]
     ...:     if len(next_sons) > 0:
     ...:         return traverse(next_sons, depth+1)
     ...:     return sons, depth

In [141]: traverse(df)
Out[141]:
(   son  father
 7    7     4.0
 9    9     4.0,
 3)