Tree Traversal Flashcards
What is tree traversal?
It is the process of visiting every tree node at least once.
What are the two main approaches for tree traversal?
Breadth First Search and Depth First Search.
What is the general direction of a breadth-first search?
The general direction is going side by side.
What is the general direction of a depth-first search?
The general direction is going down.
What do we do in BFS?
Visiting all nodes at the present depth level before moving on to nodes at the next depth level.
What are the three approaches to DFS?
In order, post-order, pre-order.
What do we do in in-order?
Visit the left subtree, root, and then the right subtree.
What do we do in pre-order?
Involves visiting all nodes on the left subtree before visiting nodes on the right subtree.
What do we do in post-order?
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 can we implement BFS?
Implement it.
- Create A Queue that will hold all the visited nodes.
- Enqueue the root node into the queue.
- Loop while there are elements in the queue.
- 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. - If the dequeued node has a right child, enqueue it.
- Return the array that holds all the values.
How can we implement DFS - Pre-order?
Implement it.
- Create a variable to store the visited node values.
- Store the root of the tree in a variable called current
3; Write a helper function that accepts a node - Push the value of the current node to the variable storing values.
- If the node has a left child, recursively call the helper function with the left child.
- If the node has a right child, recursively call the helper function with the right child.
- Invoke the helper function with the root node and return the array of values.
Implement Post Order.
What is different from pre-order and why?
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.
Implement In Order. What is different?
Do the same thing for Post Order. However, we want to push after there are no more left nodes.
When should you use DFS?
When you have a full tree. Also, useful for retrieving nodes in ascending order.
When should you use BFS?
if you want to create a copy that is easy to re-create.
