CodeSignal Technical Assessment Graph and Tree Algorithms 3

Question 1

Given an undirected tree with N nodes, how many edges does it have?

Accepted Answer

N - 1

Answer

Any tree with N nodes has exactly N - 1 edges, as each added node requires exactly one new edge.

Question 2

What is the time complexity of finding the Lowest Common Ancestor (LCA) using binary lifting after O(N log N) preprocessing?

Accepted Answer

O(log N)

Answer

Binary lifting precomputes 2^k ancestors for each node, allowing LCA queries in O(log N) time.

Question 3

In BFS on an unweighted graph, the first time a node is dequeued, its distance from the source is guaranteed to be:

Accepted Answer

The shortest path distance

Answer

BFS explores nodes in non-decreasing order of distance, so the first visit gives the exact shortest path.

Question 4

Which data structure is most commonly used to implement a disjoint set (Union-Find) with path compression and union by rank?

Accepted Answer

Array-based parent pointers

Answer

Union-Find is typically implemented with a parent array plus a rank/size array, giving near-O(1) amortized operations.

Question 5

What does the 'diameter' of a tree represent?

Accepted Answer

The longest path between any two nodes

Answer

The diameter of a tree is the length of the longest path (in edges or weight) between any two nodes.

Codesignal Practice Test