Loop in a binary tree represented in adjacency list form

Question

I attained an interview where I was asked a question as below:

You are given with parent -----> child relationships i.e. N1 ---> N2 where N1 is the parent of N2. This is nothing but representing a binary tree in adjacency list form. So I had to find whether there is a loop is present or not.

I have been mulling over this and came up with a solution:

Just need to check individual node i.e. N1 and try going deep if you see there is a edge coming back to N1 then print. Else go for next node. But the interviewer told me that it is not very efficient, can somebody help me in finding an efficient solution. Thanks.

Answer 1

You can do in a simple manner:

In a binary tree of N nodes will have N-1 edges. If it has loop then a binary tree having N nodes will have more than N-1 edges.

So you need to calculate the no of nodes and edges (parent->child) if the no_of_nodes == no_of_edges-1 than no loop else has loop.

Hope you understand.

Answer 2

Tree is a graph. So you should apply any algorithm for graph traversing, for instance BFS (breadth-first search) or DFS (depth-first search).

Both algorithms use O(V) of memory to store list of vertices (V - # of vertices) and take O(E) time to complete (E - # of edges, between V and V^2). So basically in both algorithms you need to explore all edges once.

The algorithm to identify loops in your tree is as simple as:

1) Take root node

2) Traverse through graph (breadth-first or depth-first) remembering visited nodes

3) If you visit a node that has already been visited, then you have a loop. Increment your loop counter, backtrack and go to 2

Answer 3

You need to:

1. check the graph is connected.
2. check that there's exactly E+1 vertices when you're given E edges.

You can apply Kruskal's algorithm to identify the connected components of the graph. After you've applied it, you can both check that you have exactly one connected component, and that the number of vertices is E+1.