week 7

Question 1

What is a tree

Answer 1

A simple, connected undirected graph with no simple circuits

. connected- There is a unique simple path between any two distinct vertices

Question 2

What does it mean when a tree of level n is balanced

Answer 2

The leaves are present in level n or level (n-1)

Question 3

If v is a vertex in a tree how do you find the subtree

Answer 3

make v the root
The subtree containing v is its :
.decendents
. all edges incident to these decendents

Question 4

What is an m -ary tree

Answer 4

Tree where every internal vertex( vertex with at least one child) has no more than m children

Question 5

full m -ary tree

Answer 5

tree where internal vertices has exactly m children

Question 6

What is a rooted tree

Answer 6

A tree that has one vertex designated as the root

Question 7

2 additional things about trees

Answer 7

If we add an edge to a tree, a cycle is formed
if we remove an edge its no longer connected

Question 8

2 trees are isopormopgic if

Answer 8

bijection takes:
. roots to roots
. edges to edges and non edges to non edges

Question 9

what is the length of vertex v

Answer 9

The level from root to vertex v

Question 10

height of a rooted tree

Answer 10

The maximum amount of levels that can be in the tree

Question 11

properties of binary trees of height n

Answer 11

.left and right subtrees of root are full binary trees with height <= n-1
. At least one ( not both) has height n-1