Trees Flashcards
What are the three classes of binary trees?
Complete
Full
Perfect
What makes a binary tree complete?
Every level has two children per node. The last level can be an exception to this, but if not fully filled it has to be filled left to right.
What makes a binary tree full?
Every node must have zero or two children. So there cannot be any nodes with only one child.
What are the three orders of traversal for binary trees?
In order.
Pre order
Post order
Explain in order reversal.
Visit left child.
Visit the current node.
Visit right child.
If you were printing out as you were visiting you would get an in ascending list of items from a binary search tree. (Least to greatest)
Explain pre order reversal.
Visit the current
Visit the left
Visit the right.
Explain post order traversal
Visit left
Visit right
Visit current
What are the two most common ways to search a graph?
BFS - Breadth first search
DFS - Depth first search
What is generally a reason to prefer BFS?
Looking for shortest path, don’t necessarily care about visiting all the nodes.
What is generally a reason to prefer DFS?
You know your want to visit every node.
What is the general strategy to implement DFS?
Recursion.
What is general strategy to implement BFS?
Enqueue the given node. While your queue is not empty, deque a node to visit, and enqueue it’s children/neighbors.
