# Is this data model a list or tree?

Using python syntax with below environment diagram, teacher taught us that there are 11 trees(orange boundary) in this diagram, including leaf.

It has been taught here,

lists are represented as a row of index-labeled adjacent boxes, one per element. Each box either contains a primitive value or points to a compound value. For example:

``````nested_list = [   [1, 2],    [],     [[3, False, None],[4, lambda : 5]]   ]
``````

tree is either a single value called a leaf or a sequence of trees. Typically some type restriction is placed on the leaves. E.g a tree of numbers. For example:

``````tree = [     [1, [2], 3, []],      [[4], [5,6]],       7    ]
``````

My question:

In general, Can a tree have heterogeneous type data? for example: Can I say, `abc = [1, 2, 3, 4, lamda: 5]` a tree with 5 leaves?

Note: Intention is to understand, whether tree can have heterogeneous type data

• Actually trees don't have leafs, trees have branches and branches have either smaller branches or directly leafs, so I would say abc isn't a tree, but I guess that's just a question of language. – Laurent S. Jul 16 '15 at 9:34
• @LaurentS. tree don't have leaves? what does that mean? Can you show your tree diagram with data in it? – overexchange Jul 16 '15 at 10:11
• That was my way of saying that if your tree only have leaves, it doesn't actually look like a tree. As long as no nesting is implied, I wouldn't actually speak of a tree. The same way you probably wouldn't call a real-life bag of leaves nor a single branch, a tree... – Laurent S. Jul 16 '15 at 10:34

This heavily depends on definition of list and tree.

Mathematically list doesn't mean anything and tree is just special subset of a graph.

Inferring from your question, your teacher's definition of tree is nested lists. In which case, list of nesting depth of 0 is still a tree. So

abc = [1, 2, 3, 4]

Is a tree.

In this case, the `list` is subset of `tree`. Every list is a tree, but not every tree is a list. If you have operation that only works on list, then only instances that are lists can be used as parameter, but not when they are just tree.

At least that's how it would work in math. In case of this python "pseudoexample" there is not really much difference between tree and a list. I believe you are getting confused, because your teacher is just using Python structures as definitions and not defining the terms in unambiguous mathematical terms.

• [1,2,3,4] could be thought of as a tree whose children are 4 leaves, yes. More traditionally, it is also a list with 4 items (even if some of those items were to contain themselves lists). – Neil Jul 16 '15 at 7:27
• @Neil It is also a list with four items? then why we perceive the single data model with two names 'list' and 'tree'. There should be some uniqueness between two data models, before designating name to each data model. – overexchange Jul 16 '15 at 7:59
• @overexchange See my edit. – Euphoric Jul 16 '15 at 8:05
• @overexchange: what makes you think that we perceive that model with two names? I can think of at least five: it is a list, it is a tree (because every list is a tree), it is a forest (because every tree is a forest), it is a DAG (because every forest is a DAG), it is a graph (because every DAG is a graph). – Jörg W Mittag Jul 16 '15 at 8:31
• @overexchange They can be, yes. It depends entirely on how you want to represent it. Technically a tree can be represented as just a list of pairs indicating the start and end nodes. You can and should represent the data in the way easiest for you to manage and conceptualize. – Neil Jul 16 '15 at 8:57

I think you are confusing the issue by using lambda expressions in the structure. The expression `lambda:5` is neither a list nor a number. It is a function. So the data structure in your example is not a tree of numbers, since one of the leaves is a function rather than a number.

But disregarding the lambda, the expression [1, 2, 3, 4] is a list, and also a tree according the definition of tree you provide (because it is a sequence of trees, where each tree is a leaf). This is not a contradiction, since according to the definition you provide, any list will also be a tree.

• How can list be a tree? if list is something like `[1, 2, lambda: 5]`? Because my teacher's definition of tree says that leafs have type resriction placed on the leaves – overexchange Jul 20 '15 at 15:46
• @overexchange: Depends on the type restriction, but if the type restriction is that the leaves should be numbers, then [1, 2, lambda: 5] is not a valid tree according to your definition, since a lambda is neither a sequence nor a number. – JacquesB Jul 20 '15 at 16:07
• In general, can a tree have heterogenuos type data? – overexchange Jul 20 '15 at 16:57
• @overexchange: Sure, a JSON structure for example is a tree structure with leafs of various types. – JacquesB Jul 20 '15 at 21:03
• I think JSON leaves have key value pairs. – overexchange Jul 21 '15 at 0:22