Which order do you traverse the tree with Pre Order?

Visit, Left, Right

Which order do you traverse the tree with In Order?

Left, Visit, Right

Which order do you traverse the tree with Post Order?

Left, Right, Visit

What are some real life uses of tree data structures?

- 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

What type of graph is a tree?

A connected, undirected graph with no cycles

What is a rooted tree?

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

What is the definition of a binary search tree?

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

What is the definition of an edge?

It connects to nodes

What is the definition of the root node?

The only node that has no incoming edges

What is the definition of a child node?

The set of nodes that have the same parent

What is the definition of a parent node?

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

What is the definition of a subtree?

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

What is the definition of a leaf node?

A node that has no children

What is a binary search tree used for?

To store data that is inputted in a random order automatically

What is an advantage of using a binary search tree?

Data can be traversed easily to search and extract data

How can a binary search tree be implemented?

implement three arrays:

one for the node itself

one for the node to the left

one for the node to the right

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

store -1 in an empty space

Where is the dot in a pre-order traversal?

On the left

Where is the dot in a post-order traversal?

On the right

Where is the dot in a in-order traversal?

On the bottom