Trees/Tree traversals Flashcards Preview

Paper 1 - Computer Science > Trees/Tree traversals > Flashcards

Flashcards in Trees/Tree traversals Deck (20)
Loading flashcards...
1
Q

Which order do you traverse the tree with Pre Order?

A

Visit, Left, Right

2
Q

Which order do you traverse the tree with In Order?

A

Left, Visit, Right

3
Q

Which order do you traverse the tree with Post Order?

A

Left, Right, Visit

4
Q

What are some real life uses of tree data structures?

A
  • 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
5
Q

What type of graph is a tree?

A

A connected, undirected graph with no cycles

6
Q

What is a rooted tree?

A

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

7
Q

What is the definition of a binary search tree?

A

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

8
Q

What is the definition of an edge?

A

It connects to nodes

9
Q

What is the definition of the root node?

A

The only node that has no incoming edges

10
Q

What is the definition of a child node?

A

The set of nodes that have the same parent

11
Q

What is the definition of a parent node?

A

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

12
Q

What is the definition of a subtree?

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

What is the definition of a leaf node?

A

A node that has no children

14
Q

What is a binary search tree used for?

A

To store data that is inputted in a random order automatically

15
Q

What is an advantage of using a binary search tree?

A

Data can be traversed easily to search and extract data

16
Q

How can a binary search tree be implemented?

A

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

17
Q

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

A

store -1 in an empty space

18
Q

Where is the dot in a pre-order traversal?

A

On the left

19
Q

Where is the dot in a post-order traversal?

A

On the right

20
Q

Where is the dot in a in-order traversal?

A

On the bottom