1
$\begingroup$

I'm looking for the name of a binary tree which is almost degenerate: at least one child of every interior node in the tree is a leaf.

enter image description here

(Image from Penn State course STAT 557, Data Mining, lesson 10.)

$\endgroup$
7
  • $\begingroup$ If all nodes have degree 2 then what you get is a disjoint union of cycles, rather than a binary tree. $\endgroup$ Commented Aug 22, 2015 at 11:31
  • $\begingroup$ Why "almost" degenerated? $\endgroup$
    – Raphael
    Commented Aug 22, 2015 at 12:02
  • $\begingroup$ "almost" degenerated because all nodes have degree 2, except the leave nodes which have degree 0. $\endgroup$
    – user7060
    Commented Aug 22, 2015 at 12:26
  • $\begingroup$ The leaves of the tree in your image have degree one, not degree zero. $\endgroup$
    – Juho
    Commented Aug 22, 2015 at 13:19
  • 2
    $\begingroup$ If we interpret the tree as an undirected graph, then the degree of a vertex $v$ is the number of vertices adjacent to $v$. So every leaf has degree 1. Perhaps we would agree if we looked at the tree as a directed graph. Then, one could say the out-degree of the leaf is 0 (but the in-degree is 1). $\endgroup$
    – Juho
    Commented Aug 22, 2015 at 19:47

3 Answers 3

3
$\begingroup$

This is a binary tree, when by a binary tree we mean a tree where each vertex has at most 2 children. In other words, you have a tree of maximum degree 3. Also, generally a tree that has a dominating path is a caterpillar.

$\endgroup$
1
  • $\begingroup$ Thanks juho. i'm looking for a name describing a tree where all inner nodes have two children. $\endgroup$
    – user7060
    Commented Aug 24, 2015 at 6:34
3
$\begingroup$

I've seen this type of tree called a comb. But this isn't such a widespread term that you can use it without defining it.

Technically, a nested data structure where every node has one child that's a leaf, with the list always on the same side, is a list. When the last node has two leaves the one that's not on the usual leaf side is not a special “null” marker, it's an improper list. But this terminology works for data structures, it sounds strange when applied to a decision tree.

$\endgroup$
1
  • $\begingroup$ Thanks Gilles. There isn't a particular name for such a tree ? $\endgroup$
    – user7060
    Commented Aug 24, 2015 at 6:33
0
$\begingroup$

You mean a rooted tree for which all interior nodes have two children?

These are called extended binary trees, and the one you have would be the extended binary tree with maximum height among all such with $n$ nodes.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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