MHB Growing More Trees to Sustainable Living

[Brian82784]

Just checking to see if my work is correct for these 5.

 

[Evgeny.Makarov]

I come into contact with tree structures only occasionally, so I don't remember all definitions. Besides, some concepts have been used in different senses in different sources.

1a) This is correct if levels are counted from 1. I think it is more likely that the root has level 0.

1b-d) Correct.

2) Correct.

3) According to NIST, a complete tree is one "in which every level, except possibly the deepest, is entirely filled. At depth $n$, the height of the tree, all nodes are as far left as possible". This grouping to the left means that no only a child has to be added to v1, but also it must have three children of its own. The problem statement does not make it clear how to write this. A similar observation applies to v2: if children are added to the left of v6, then they themselves have to have three children each.

Also, there is more than one way to turn this tree into a complete one: for example, one could add from 0 to 3 children grouped left to v7 and 0 children to v8 and v9. One could add 0 or 1 child to v6 (zero if no children are added to v7--v9). As for v10 and v11, they should definitely not have children.

This problem does not seem to be formulated very well. Perhaps you have a different definition of a complete tree.

Edit: Forgot 4) and 5). I am not sure what T(v3) denotes and what the difference is with (T, v3). You should review the definition of tree height in your source, but I think it's the maximum number of edges from the root to a leave. Then the height of the whole tree in the second picture is 2.

 

[johng1]

Hi,
I agree with Markov; the definition of complete tree is as specified in his link. Also unless you have misinterpreted the definitions, your text/instructor is "marching to his own drummer". For example, the height of a tree with one node is 0. The following tree is the result of augmenting your original tree to a complete tree; the color coding indicates the nodes which are added.

 

[Brian82784]

Okay so uploaded the questions they way they were before I did anything. And then I re-did my work, and attached my answers. I hope I did it right!

 

[Evgeny.Makarov]

The number of vertices that have to be added to v4 and v5 is incorrect. I repeat the remarks that one must add leaves to some added vertices and that this tree can be made complete in several ways. Also, as I said in post #2,

I am not sure what T(v3) denotes and what the difference is with (T, v3).

What do you denote by (T, v3) and T(v3)?