CodeSignal Technical Assessment Graph and Tree Algorithms 2

Question 1

In Dijkstra's algorithm using a min-heap, what is the time complexity for a graph with V vertices and E edges?

Accepted Answer

O((V + E) log V)

Answer

Using a binary min-heap, each edge relaxation costs O(log V), giving O((V + E) log V) overall.

Question 2

Which traversal of a Binary Search Tree visits nodes in sorted ascending order?

Accepted Answer

In-order

Answer

In-order traversal (left → root → right) on a BST always visits keys in non-decreasing order.

Question 3

A graph has a cycle if and only if DFS produces a back edge. What does a 'back edge' connect?

Accepted Answer

A node to an ancestor in the DFS tree

Answer

A back edge connects a vertex to one of its ancestors in the DFS recursion stack, forming a cycle.

Question 4

What is the maximum number of nodes in a complete binary tree of height h?

Accepted Answer

2^(h+1) - 1

Answer

A complete binary tree of height h has at most 2^(h+1) - 1 nodes (all levels filled).

Question 5

Which algorithm finds the Minimum Spanning Tree by always adding the globally smallest edge that does not form a cycle?

Accepted Answer

Kruskal's

Answer

Kruskal's algorithm sorts all edges and greedily adds the smallest edge that connects two different components.

Codesignal Practice Test