Amazon Interview Question
SDE-2sCountry: India
Interview Type: In-Person
In this particular type of binary tree representation, a node can appear only thrice. As a child of parent and parent of two of its children. If the three appearance is violated, then binary tree has a loop. Consider the following binary tree. 8 appears 4 times and hence btree has loop.
10,8 8,9 12,11 12,20 10,12 20,15 20,25 8,5 5,3 5,7 3,8
If given list is:
(1, 2), (1, 3)
(2, 4), (2, 5)
(3, 6), (3, 7)
Given list can be converted into adjacency list:
1 --> 2, 3
2 --> 4, 5
3 --> 6, 7
4 -->
5 -->
6 -->
7 -->
On this list, we can run DFS / BFS to find we there is any revisit on a node. If a node is revisited then there is a loop else no loop.
Tree is a directed acyclic graph. So, there should have only one path from root to any node in the tree. If this property is violated then the graph is not a tree and might have the potential chance for having a loop. We can easily check this by checking number of incoming edges to a node.
- zahidbuet106 December 05, 20131) If a non-root node has more than one incoming edge then loop exists only if the edge is from a child to an ancestor.
2) If the root contains an incoming edge then loop surely exists.
If we have a tree like
a
/ \
b c
/ \
d e
Now assume there is an edge from d to b (d, a). This edge will create a loop according to (2). Now assume an edge from d to b: (d, b). Then there will be a loop according to (1). But if e have an edge from e to c : (e,c) then there exist no loop although the tree is not tree anymore as there are more than one path from root to c.