Exploring Trees and Graph Algorithms

What is a binary search tree and how does it differ from a regular binary tree?

• A binary search tree is a type of graph structure.

• A binary search tree is a binary tree with ordered nodes, allowing efficient search, while a regular binary tree has no such ordering.

• A binary search tree is a tree with only left children.

• A binary search tree allows duplicate values, while a binary tree does not.

Explain the process of breadth-first search (BFS) in a graph.

• BFS only explores the deepest nodes first before backtracking.

• BFS requires a binary tree structure to function properly.

• BFS visits nodes in a random order using a stack.

• BFS explores all neighbors of a node before moving to the next level, using a queue for tracking nodes.

What is the time complexity of Floyd's algorithm for finding shortest paths?

• O(V^4)

• O(V^2)

• O(V^3)

• O(V log V)

Describe Dijkstra's algorithm and its application in finding the shortest path in a weighted graph.

• Dijkstra's algorithm uses a depth-first search approach to explore all possible paths.

• Dijkstra's algorithm is only applicable to unweighted graphs and cannot handle weights.

• Dijkstra's algorithm is used to find the shortest path in a weighted graph by exploring nodes based on the smallest cumulative weight from the starting node.

• Dijkstra's algorithm finds the longest path in a graph by visiting nodes in random order.

How do you insert a new node into a binary search tree?

• Insert the new node at the root of the tree.

• Delete the smallest node before inserting the new one.

• Insert the new node in the correct position based on its value.

• Always place the new node as the left child.

What are the advantages of using BFS over DFS in graph traversal?

• BFS can only be used on directed graphs.

• DFS guarantees finding the shortest path in unweighted graphs.

• BFS is better for finding the shortest path in unweighted graphs and systematically explores all nodes at the current depth.

• DFS is always faster than BFS for all types of graphs.

Explain how Floyd's algorithm can be used to find all pairs shortest paths.

• Floyd's algorithm finds all pairs shortest paths by iteratively updating a distance matrix based on intermediate vertices.

• Floyd's algorithm is limited to finding shortest paths in directed graphs only.

• Floyd's algorithm requires a priority queue to function effectively.

• Floyd's algorithm only finds the shortest path from a single source to all other vertices.

What is the main difference between Dijkstra's algorithm and Prim's algorithm?

• Dijkstra's algorithm is used for undirected graphs, while Prim's algorithm is for directed graphs.

• Dijkstra's algorithm finds the shortest path, Prim's algorithm finds the minimum spanning tree.

• Both algorithms find the shortest path in a graph.

• Dijkstra's algorithm finds the minimum spanning tree, Prim's algorithm finds the shortest path.

How does a binary search tree maintain its properties during deletion?

• A binary search tree deletes nodes without any replacement.

• A binary search tree maintains its properties during deletion by replacing the deleted node with its in-order predecessor or successor when it has two children.

• A binary search tree only removes leaf nodes without adjustments.

• A binary search tree maintains balance by rotating nodes during deletion.

Describe the steps involved in implementing Dijkstra's algorithm using a priority queue.

• Initialize a priority queue, set distances, extract min node, update neighbors, repeat.

• Initialize a stack, set weights, extract max node, update parents, finish.

• Initialize a queue, set distances to zero, extract random node, update all neighbors, repeat.

• Create a list of nodes, set random values, extract random node, update all, stop.