2
$\begingroup$

I've written a recursive function of a tree, and I would like to know what it's called! It's not quite the same as the height or the width of a tree, but it seems kind of like a width.

Assuming the tree $T$ is binary, we can define the function $f(T)$ as follows. If $T$ has a only a single node, let $f(T) = 1$. Otherwise, let $T_0$ and $T_1$ be the two trees rooted at the child nodes $T$'s root. If $f(T_0) = f(T_1)$, then let $F(T) = F(T_0) + 1$; otherwise, let $f(T) = \max(f(T_0), f(T_1))$.

The function $f$ is generalized as follows to trees that are not necessarily binary. As before, let $f(T) = 1$ when $T$ has no edges. Otherwise, let $T_0, \dots, T_k$ be the $k+1$ subtrees rooted at the child nodes of $T$'s root, sorted by descending values of $f$. Then let $f(T) = \max_i(f(T_i) + i)$.

Improve this question
$\endgroup$
0
2
$\begingroup$

This is basically the Strahler number, which is great because now I can call my function ComputeStrahlerNumber instead of keeping the profane function name I was using as a placeholder.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Is the Strahler number also defined for trees that are not binary? BTW what do you mean by "Baader-Meinhof-ly"? This is a strange expression to use. $\endgroup$ – babou Oct 5 '14 at 21:11
  • $\begingroup$ @babou The phenomenon where you learn something for the first time and then immediately afterwards you see that thing again is known as the Baader-Meinhof phenomenon. I used that expression because I first learned about the Strahler number using google searches to try answering this cs.stackexchange question, and then soon afterwards another cs.stackexchange question whose answer also involved the Strahler number was posted. $\endgroup$ – guest Oct 5 '14 at 21:40
  • $\begingroup$ @babou Yes if you read the Wikipedia page you can see that the Strahler number is defined for trees that are not binary. Interestingly, the answers to the stackexchange questions both use the same generalization as each other, but this generalization is slightly different than the Strahler number generalization as defined on Wikipedia. $\endgroup$ – guest Oct 5 '14 at 21:46
  • $\begingroup$ "Baader-Meinhof phenomenon" is a strange name. But that was not the only coincidence ... I mean the reference to Strahler number (?). Wikipedia does define Strahler number for non binary nodes, but the definition is different from yours. Yours seems more consistent with the possibility of binarizing the tree. $\endgroup$ – babou Oct 5 '14 at 22:00
  • $\begingroup$ The term Wikipedia lists, "frequency illusion", may have been the better choice (even if it's still not clear to me what value it adds). I appreciate a light tone, but it should add something for every reader (in this case, only you experienced the phenomenon). (cc @babou) That said, please take discussion to Computer Science Chat. $\endgroup$ – Raphael♦ Oct 6 '14 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.