<p>The title of this question pretty much says it all.</p>
<p>I would like to know if there is some standard name for trees in which, if any two nodes are siblings, then either they are both leaves, or they are both non-leaves.</p>
<p>One variation of the same situation occurs in trees with two <em>types</em> of nodes, such that one of these two types <em>can</em> have children, and the other one cannot.  (An everyday example of this is a simple file system consisting exclusively of &quot;folders&quot; and &quot;files&quot;.)  In this case, the condition in the title could be modified to requiring that siblinghood can happen only between nodes of the same type.  (With this variation, the number of children a node happens to have plays no role in whether the tree containing tree satisfies the condition or not.)</p>
<p>Is there a standard name for either of the two variations described above?</p>
<hr />
<p><strong>P.S.</strong> Should I post this in math.stackexchange.com instead?</p>

CC BY-SA 4.0
2021-12-02T18:44:31.343Z
The generating function for $n$-node trees in the binary case, if I'm mathing right, satisfies $K_{n+1}=2K_n + \sum_{i=2}^{n-2} K_iK_{n-i}$ for $n\gt 3$, with $K_1=1$, $K_2=2$, $K_3=5$; continuing this gives $1,2,5,10,24,68$ which doesn't show up on OEIS.
Steven Stadnicki
CC BY-SA 4.0
2021-12-02T19:19:36.170Z
@StevenStadnicki: pardon my ignorant question, but what does $K_n$ stand for?  At first I thought it would be the number of $n$-node binary trees that satisfy the condition described in my post, but if that's the case, then it would seem to me that $K_2 = 0$, because the smallest binary tree with more than 1 node would be the one with 3 nodes (one parent and its two children).  Here I am assuming that a "binary tree" is one where all nodes are either leaves (i.e. they have 0 children) or have exactly 2 children.
kjo
CC BY-SA 4.0
2021-12-02T19:23:07.017Z
I'm thinking about a very CS-ish version of 'binary tree' where each node has explicitly left and right paths from it, but those paths can be null; the two-node trees in this model are essentially / and \ . Your assumed version is usually known by the name 'full binary tree'; see https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees . (And yes, my $K_n$ is the number of valid trees on $n$ nodes for my version of the definitions)
Steven Stadnicki
<ds.data-structures>
Is there a name for trees were siblinghood cannot happen between a leaf and a non-leaf?
kjo
# Is there a name for trees were siblinghood cannot happen between a leaf and a non-leaf?

(Asked by: username_0 on 2020-09-29)

The title of this question pretty much says it all.

I would like to know if there is some standard name for trees in which, if any two nodes are siblings, then either they are both leaves, or they are both non-leaves.

One variation of the same situation occurs in trees with two *types* of nodes, such that one of these two types *can* have children, and the other one cannot. (An everyday example of this is a simple file system consisting exclusively of "folders" and "files".) In this case, the condition in the title could be modified to requiring that siblinghood can happen only between nodes of the same type. (With this variation, the number of children a node happens to have plays no role in whether the tree containing tree satisfies the condition or not.)

Is there a standard name for either of the two variations described above?

---

**P.S.** Should I post this in math.stackexchange.com instead?

**Tags:** ds.data-structures

> **Comments:**
> **username_1**: The generating function for $n$-node trees in the binary case, if I'm mathing right, satisfies $K_{n+1}=2K_n + \sum_{i=2}^{n-2} K_iK_{n-i}$ for $n\gt 3$, with $K_1=1$, $K_2=2$, $K_3=5$; continuing this gives $1,2,5,10,24,68$ which doesn't show up on OEIS.  
> **username_0**: @StevenStadnicki: pardon my ignorant question, but what does $K_n$ stand for?  At first I thought it would be the number of $n$-node binary trees that satisfy the condition described in my post, but if that's the case, then it would seem to me that $K_2 = 0$, because the smallest binary tree with more than 1 node would be the one with 3 nodes (one parent and its two children).  Here I am assuming that a "binary tree" is one where all nodes are either leaves (i.e. they have 0 children) or have exactly 2 children.  
> **username_1**: I'm thinking about a very CS-ish version of 'binary tree' where each node has explicitly left and right paths from it, but those paths can be null; the two-node trees in this model are essentially / and \ . Your assumed version is usually known by the name 'full binary tree'; see https://en.wikipedia.org/wiki/Binary_tree#Types_of_binary_trees . (And yes, my $K_n$ is the number of valid trees on $n$ nodes for my version of the definitions)  

---

## 0 answers

