Trees

Question 1

Leaf

Answer 1

A vertex of degree 1 in a tree

Question 2

What property does an undirected graph need to be a tree

Answer 2

An undirected graph is a tree if and only if there is exactly one path between every pair of vertices

Question 3

What are the three equivalent definitions of a tree

Answer 3

A connected simple graph without loops or cycles
A graph with a unique path between every pair of vertices
A connected graph with n - 1 edges for n vertices

Question 4

Rooted tree

Answer 4

A tree with one designated vertex called the root, from which levels are defined for other vertices

Question 5

How is the level of a vertex defined in a rooted tree

Answer 5

The level of a vertex is the length of the unique path from the root to that vertex

Question 6

What is the height of a rooted tree

Answer 6

Number of edges between the start to end vertices

Question 7

In a rooted tree, what is the parent of a vertex at level e

Answer 7

The parent is the unique neighbour of the vert at level e -1

Question 8

In a rooted tree, what is a child of a vertex at level 3

Answer 8

A child is a neighbour of the vertex at level e + 1

Question 9

What is binary tree

Answer 9

A binary tree where every vertex has at most 2 children

Question 10

What is a full binary tree

Answer 10

A binary tree where every vertex has either 0 or 2 children