Trees/Tree traversals

Question 1

Which order do you traverse the tree with Pre Order?

Answer 1

Visit, Left, Right

Question 2

Which order do you traverse the tree with In Order?

Answer 2

Left, Visit, Right

Question 3

Which order do you traverse the tree with Post Order?

Answer 3

Left, Right, Visit

Question 4

What are some real life uses of tree data structures?

Answer 4

• manipulating hierarchical data (such as folder structures /OS may use for file directories)
• making information easy to search (binary search trees)
• manipulating sorted lists of data

Question 5

What type of graph is a tree?

Answer 5

A connected, undirected graph with no cycles

Question 6

What is a rooted tree?

Answer 6

A tree that has a designated node as the root of the tree

Question 7

What is the definition of a binary search tree?

Answer 7

A rooted tree, that has a maximum of two children per node

Question 8

What is the definition of an edge?

Answer 8

It connects to nodes

Question 9

What is the definition of the root node?

Answer 9

The only node that has no incoming edges

Question 10

What is the definition of a child node?

Answer 10

The set of nodes that have the same parent

Question 11

What is the definition of a parent node?

Answer 11

A node is a parent of all the nodes it connects with outgoing edges

Question 12

What is the definition of a subtree?

Answer 12

• The set of nodes and edges comprised of a parent and all descendants of the parent.
• A subtree may also be a leaf

Question 13

What is the definition of a leaf node?

Answer 13

A node that has no children

Question 14

What is a binary search tree used for?

Answer 14

To store data that is inputted in a random order automatically

Question 15

What is an advantage of using a binary search tree?

Answer 15

Data can be traversed easily to search and extract data

Question 16

How can a binary search tree be implemented?

Answer 16

implement three arrays:
one for the node itself
one for the node to the left
one for the node to the right

Question 17

How could we indicate there’s no child node in a space in an array?

Answer 17

store -1 in an empty space

Question 18

Where is the dot in a pre-order traversal?

Answer 18

On the left

Question 19

Where is the dot in a post-order traversal?

Answer 19

On the right

Question 20

Where is the dot in a in-order traversal?

Answer 20

On the bottom