Tree Traversal Flashcards

1
Q

What is tree traversal?

A

It is the process of visiting every tree node at least once.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the two main approaches for tree traversal?

A

Breadth First Search and Depth First Search.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

What is the general direction of a breadth-first search?

A

The general direction is going side by side.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What is the general direction of a depth-first search?

A

The general direction is going down.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What do we do in BFS?

A

Visiting all nodes at the present depth level before moving on to nodes at the next depth level.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What are the three approaches to DFS?

A

In order, post-order, pre-order.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What do we do in in-order?

A

Visit the left subtree, root, and then the right subtree.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What do we do in pre-order?

A

Involves visiting all nodes on the left subtree before visiting nodes on the right subtree.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What do we do in post-order?

A

Nodes are visited starting from the leftmost leaf, then the right side, then its parent, next do it to the right side, and finally, we end at the root.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

How can we implement BFS?
Implement it.

A
  1. Create A Queue that will hold all the visited nodes.
  2. Enqueue the root node into the queue.
  3. Loop while there are elements in the queue.
  4. Dequeue the current node, and store it inside an array that will hold its values.
    6 . If the dequeued node has a left child, enqueue it.
  5. If the dequeued node has a right child, enqueue it.
  6. Return the array that holds all the values.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

How can we implement DFS - Pre-order?
Implement it.

A
  1. Create a variable to store the visited node values.
  2. Store the root of the tree in a variable called current
    3; Write a helper function that accepts a node
  3. Push the value of the current node to the variable storing values.
  4. If the node has a left child, recursively call the helper function with the left child.
  5. If the node has a right child, recursively call the helper function with the right child.
  6. Invoke the helper function with the root node and return the array of values.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Implement Post Order.
What is different from pre-order and why?

A

Do the same thing as pre-order. however, for the traverse helper function, we want to push at the end.

We do this because, once we reach the left, there are no more nodes to the right or left, so it just pushes the node to the farthest left.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Implement In Order. What is different?

A

Do the same thing for Post Order. However, we want to push after there are no more left nodes.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

When should you use DFS?

A

When you have a full tree. Also, useful for retrieving nodes in ascending order.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

When should you use BFS?

A

if you want to create a copy that is easy to re-create.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Why is BFS bad?

A

It takes a lot of memory when iterating through a full tree.

17
Q

Why is DFS bad?

A

For one-sided deep trees, it can take a lot of memory.