Trees

Question 1

Tree

Answer 1

An undirected graph that contains no cycles and is connected

Question 2

Trees vs Graphs

Answer 2

Cycles: Graphs contain cycles, trees don’t
Connectivity: Graphs can be disconnected, trees are always connected
Hierarchy: Trees have a hierarchical structure, graphs don’t

Question 3

Subtree

Answer 3

A tree who whose root is a node in another tree

Question 4

Binary Trees

Answer 4

A rooted tree in which every parent has at most 2 children

Question 5

Full Binary Tree

Answer 5

A binary tree in which each parent has exactly 2 children

Question 6

Full m-ary tree

Answer 6

A tree in which each parent has exactly m children

Question 7

If a full binary tree has n internal vertices, what is the formula to calculate the total vertices?

Answer 7

2n + 1

Question 8

If a full m-ary tree has n internal vertices, what is the formula to calculate the total vertices?

Answer 8

mn + 1

Question 9

How to calculate the number of leaves based on a tree’s height?

Answer 9

If h >= 0, then t <= 2^h

Question 10

Pre-order Traversal

Answer 10

1. Visit the root
2. Pre-order (left subtree)
3. Pre-order (right subtree)

Question 11

In-order Traversal

Answer 11

1. In-order (left subtree)
2. Visit the root
3. In-order (right subtree)

Question 12

Post-order Traversal

Answer 12

1. Post-order (left subtree)
2. Post-order (right subtree)
3. Visit the root

Question 13

Sorting trees rules

Answer 13

left child < parent
right child > parent

Question 14

If left child = parent key then…

Answer 14

left child value < parent value

Question 15

If right child value = parent key then…

Answer 15

right child value > parent value