Graph and Tree Algorithms Flashcards
7 cards from real CodeSignal Technical Assessment practice questions. Tap to flip, then mark Knew It or Still Learning — missed cards come back until you master them.
Read the first 7 Graph and Tree Algorithms flashcards as text
In Dijkstra's algorithm using a min-heap, what is the time complexity for a graph with V vertices and E edges?
Answer: O((V + E) log V)
Using a binary min-heap, each edge relaxation costs O(log V), giving O((V + E) log V) overall.
Which traversal of a Binary Search Tree visits nodes in sorted ascending order?
Answer: In-order
In-order traversal (left → root → right) on a BST always visits keys in non-decreasing order.
A graph has a cycle if and only if DFS produces a back edge. What does a 'back edge' connect?
Answer: A node to an ancestor in the DFS tree
A back edge connects a vertex to one of its ancestors in the DFS recursion stack, forming a cycle.
What is the maximum number of nodes in a complete binary tree of height h?
Answer: 2^(h+1) - 1
A complete binary tree of height h has at most 2^(h+1) - 1 nodes (all levels filled).
Which algorithm finds the Minimum Spanning Tree by always adding the globally smallest edge that does not form a cycle?
Answer: Kruskal's
Kruskal's algorithm sorts all edges and greedily adds the smallest edge that connects two different components.
In a directed graph, what does Kosaraju's algorithm compute?
Answer: Strongly Connected Components (SCCs)
Kosaraju's runs DFS twice—once on the original and once on the transposed graph—to identify all SCCs.
What property must a graph satisfy for a topological sort to exist?
Answer: It must be a DAG (Directed Acyclic Graph)
Topological ordering is only defined for Directed Acyclic Graphs; any cycle makes a linear ordering impossible.