⸻
Tree Answers
Basic Questions
1. What is the difference between a binary tree and a binary search tree (BST)?
• A binary tree is a tree where each node has at most two children (left and right).
• A binary search tree (BST) is a binary tree with an additional property: for any node, the left subtree contains only nodes with values smaller than the node’s value, and the right subtree contains only nodes with values larger than the node’s value.
⸻
2. In a binary tree, what are the three types of depth-first traversal? How do they differ?
• Preorder: Visit the root → Left subtree → Right subtree.
• Inorder: Left subtree → Visit the root → Right subtree.
• Postorder: Left subtree → Right subtree → Visit the root.
⸻
3. How would you identify whether a given tree is a full binary tree or a complete binary tree?
• A full binary tree is a tree where every node has either 0 or 2 children.
• A complete binary tree is a tree where all levels are fully filled except possibly the last level, which must be filled from left to right.
⸻
4. What is the difference between the height and depth of a tree node?
• Height of a node = Number of edges on the longest path from that node to a leaf.
• Depth of a node = Number of edges from the root to that node.
⸻
5. What is the advantage of using a binary heap over a regular binary tree for implementing a priority queue?
• A binary heap ensures efficient insertion and extraction of the minimum/maximum element in O(log n) time, whereas a regular binary tree may take longer if it’s unbalanced.
⸻
Intermediate Questions
6. You are asked to find the lowest common ancestor (LCA) of two nodes in a binary tree. What are the possible approaches, and which one would be most efficient?
• Approach 1: Recursive approach using postorder traversal (O(n) time).
• Approach 2: Store parent pointers and find common ancestors (O(h) time, where h is the height).
• Best Approach: Postorder traversal is efficient and direct.
⸻
7. How would you check if a given binary tree is balanced? What is the time complexity of the most efficient solution?
• Use a recursive approach that returns both height and balance status simultaneously.
• Efficient solution: O(n) time using bottom-up recursion.
⸻
8. If you are given a preorder and inorder traversal of a binary tree, how would you reconstruct the tree? What data structure would be helpful here?
• Build the tree recursively by identifying the root from preorder and partitioning left/right subtrees using inorder.
• A hashmap for inorder index lookup improves efficiency to O(n).
⸻
9. Explain the Morris Traversal approach for in-order traversal. How does it avoid using a stack or recursion?
• Morris Traversal creates temporary links (threads) to predecessors and modifies pointers to avoid extra memory.
• Time: O(n), Space: O(1).
⸻
10. How can you convert a binary search tree (BST) into a balanced BST with minimal height? Outline the steps.
1. Perform an in-order traversal to get a sorted list of elements.
2. Build a balanced BST using the sorted list (similar to binary search).
3. Time complexity: O(n).
⸻
Graph Answers
Basic Questions
1. What is the difference between a directed and an undirected graph? Give an example of when you would use each.
• Directed graph: Edges have a direction (e.g., web links).
• Undirected graph: Edges have no direction (e.g., social networks).
⸻
2. Explain the difference between a weighted and an unweighted graph. How does this affect traversal algorithms?
• Weighted graph: Edges have a weight or cost. Algorithms like Dijkstra’s or Bellman-Ford are used.
• Unweighted graph: BFS is sufficient for shortest path.
⸻
3. What are the differences between an adjacency matrix and an adjacency list? When would you use one over the other?
• Adjacency Matrix: O(1) edge lookup, O(V²) space (good for dense graphs).
• Adjacency List: O(V + E) space, better for sparse graphs.
⸻
4. What is a connected graph? How would you check if a graph is connected?
• A graph is connected if there is a path between every pair of nodes.
• Use DFS or BFS to check connectivity.
⸻
5. What is a cycle in a graph? How would you detect a cycle in a directed graph versus an undirected graph?
• A cycle is a path that starts and ends at the same node.
• Directed graph: Use DFS with a recursion stack.
• Undirected graph: Use DFS while checking parent nodes.
⸻
Intermediate Questions
6. You need to find the shortest path in an unweighted graph. Which algorithm would you use and why?
• Use BFS because it explores nodes layer by layer.
• Time: O(V + E).
⸻
7. If you are tasked with finding the shortest path in a weighted graph where some weights are negative, which algorithm would you use? Why wouldn’t Dijkstra’s algorithm work here?
• Use Bellman-Ford because it handles negative weights.
• Dijkstra assumes non-negative weights, so it fails with negatives.
⸻
8. How would you detect a negative weight cycle in a graph? Which algorithm would you apply?
• Use Bellman-Ford – if a value updates after |V| − 1 relaxations, a cycle exists.
⸻
9. Explain the differences between Depth-First Search (DFS) and Breadth-First Search (BFS). In which scenarios would one be more suitable than the other?
• DFS: Good for pathfinding and cycle detection.
• BFS: Good for shortest path and level-order traversal.
⸻
10. How would you find the minimum spanning tree (MST) of a graph? What are two common algorithms for this problem, and how do they differ?
• Kruskal’s Algorithm: Sort edges, use union-find.
• Prim’s Algorithm: Use priority queue for greedy edge selection.
• Both are O(E log V).
⸻
Advanced Thinking
11. You are tasked with finding the number of strongly connected components (SCCs) in a directed graph. Which algorithm would you use and why?
• Use Kosaraju’s Algorithm (or Tarjan’s).
• Kosaraju: Two-pass DFS.
⸻
12. How would you determine if a directed graph contains a topological ordering? If it does, how would you generate one?
• Use Kahn’s Algorithm (BFS) or DFS for topological sort.
• If no cycle exists, a topological order is possible.
⸻
13. You need to find the shortest path between all pairs of nodes in a graph. Which algorithm would you use, and what is its time complexity?
• Use Floyd-Warshall (O(V³)).
⸻
14. How would you solve the problem of finding the number of connected components in an undirected graph?
• Use DFS or BFS and count components.
• Time: O(V + E).
⸻
15. Explain how Dijkstra’s algorithm can be modified to find the second shortest path between two nodes in a graph.
• Run Dijkstra once.
• Remove the shortest edge from the shortest path, then rerun Dijkstra.