Search Algorithms

Breadth First Search Definition

Search all the leaves in a tree level before moving onto the next level

Depth First Search Definition

Search leaf nodes to leaf node until you reach a node with no leaf nodes. Then you backtrack until you come across a node with a leaf node you haven’t yet visited, then move down leaf nodes the same way.

Breadth First Search Implementation in Python

Start a queue with the root node as the first item.

Start a while loop over the queue, as long as the queue has items.

Pop the front of the queue, print, and add all neighbors to the queue.

Depth First Search Implementation in Python Recursively

Track visited nodes with a set.

Define a DFS function that takes cur_node and visited_nodes as params.

Mark cur_node as visited.

For every neighbor, call DFS function with that neighbor and the updated visited_nodes.

Depth First Search Implementation in Python Iteratively

Init a stack with root node in it.

Init a set.

While stack is not empty, pop, mark popped node as visited, then add all non-visited neighbors to stack.

What search algorithm do you want to use to find the shortest path for a graph with unweighted edges? Why?

BFS, because since it goes level by level, it minimizes the distance traveled to find the target.

What is the space and time complexity of BFS? Why?

Time: O(V + E) because, at worst, we visit every node and edge at least once.

Space: O(V) because, at worst, we store every vertex in our queue or distance graph.

In BFS, how would you track and display the actual route from the root to your target node?

With a parent mapping.

Every time you visit a node and are inserting its neighbors into the queue, insert each neighbor into the parent mapping with the key being the neighbor, and the current node being the value.

In a wide and deep graph, would DFS or BFS be more space efficient?

DFS, Because DFS only needs to keep track of the neighbors down a single path within the tree, whereas BFS needs to keep track of all ancestors in a single level.

Do trees/graphs tend to grow more in width or height as they grow?

Width, because with most common applications of trees/graphs, such as file systems, social networks, etc, a single node will connect to multiple, causing the graph to grow exponentially wide.

What is pre, in, and post order traversing in DFS?

Pre-order: visit node —> left —> right, print nodes as they are visited

In-order: left —> visit node —> right, starts printing once it reaches the bottom of the left subtree

Post-order: left —> right —> visit node, prints the entire left and right subtree of each node before printing that node (left to right scrubbing at the bottom)

Think of each node as having these written next to them, and crossing them out as they are done

Pre-Order traversal

ABDECFGH

In-Order traversal

DBEAFCHG

Post-Order traversal of this tree

DEBFHGCA

How would you traverse a Binary Search Tree if you wanted to serialize it? Why?

Pre-Order, because it prints the shape of the tree as you travel through it.

When you have a Binary Search Tree, which traversal should you use for getting the values in sorted order?

In-order

Why is post-order traversal good for memory clearing?

Because it visits the left and right children and clears them before clearing the parent, leaving no hanging children.

What is the required structure for a binary search tree?

Every node's left child is a lower value, and every right child is a higher value.

How to perform binary search on a binary tree in python?

Recursive function that accepts a cur_node and a target, if the cur_node is the target, return cur_node, else if the target is < cur_node, return recursion of the left child, else the right. If the cur_node is None, return None.

Define the add_node function of a binary tree in python, recursively. Explain how the recursion stack would look.

Define a recursive function that accepts a cur_node and a new node/data.

Call this function with the root node and the new node.

If the cur_node is None, return the new node.

If the new_node < cur_node, cur_node.left = recursive(cur_node.left, new_node), else right

Explanation:

Function is added to the stack for every