Menu
One of my favorite interview questions is
In O(n) time and O(1) space, determine whether a linked list contains a cycle.
This can be done using Floyd's cycle-finding algorithm.
My question is whether it's possible to get such good time and space guarantees when trying to detect whether a binary tree contains a cycle. That is, if someone gives you a struct definition along the lines of
struct node {
node* left;
node* right;
};
How efficiently can you verify that the given structure is indeed a binary tree and not, say, a DAG or a graph containing a cycle?
Is there an algorithm that, given the root of a binary tree, can determine whether that tree contains a cycle in O(n) time and better than O(n) space? Clearly this could be done with a standard DFS or BFS, but this requires O(n) space. Can it be done in O(√n) space? O(log n) space? Or (the holy grail) in just O(1) space? I'm curious because in the case of a linked list this can be done in O(1) space, but I've never seen a correspondingly efficient algorithm for this case.
354
Cycles in a binary tree can be detected by DFS(in preorder) - if there's a cycle, there must be a node has a child node that is already been accessed before(i.e. a right hand node linked to the left hand node). A unordered_set can be used to record the nodes that have been accessed.
Use DFS from every unvisited node. Depth First Traversal can be used to detect a cycle in a Graph.
Cycle detection The existence of a cycle in directed and undirected graphs can be determined by whether depth-first search (DFS) finds an edge that points to an ancestor of the current vertex (it contains a back edge). All the back edges which DFS skips over are part of cycles.
BFS wont work for a directed graph in finding cycles. Consider A->B and A->C->B as paths from A to B in a graph. BFS will say that after going along one of the path that B is visited. When continuing to travel the next path it will say that marked node B has been again found,hence, a cycle is there.
You can't even visit each node of a real, honest-to-god, cycle-free tree in O(1) space, so what you are asking for is clearly impossible. (Tricks with modifying a tree along the way are not O(1) space).
If you are willing to consider stack-based algorithms, then a regular tree walk can be easily modified along the lines of Floyd's algorithm.
95
it is possible to test in logarithmic space if two vertices of a graph belong to the same connected component (Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM 55 (4): Article 17, 24 pages, doi:10.1145/1391289.1391291). A connected component is cyclic; hence if you can find two vertices in a graph that belong to the same connected component there is a cycle in the graph. Reingold published the algorithm 26 years after the question of its existence was first posed (see http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29). Having an O(1) space algorithm sounds unlikely given that it took 25 years to find a log-space solution. Note that picking two vertices from a graph and asking if they belong to a cycle is equivalent to asking if they belong to a connected component.
This algorithm can be extended to a log-space solution for graphs with out-degree 2 (OP: "trees"), as it is enough to check for every pair of a node and one of its immediate siblings if they belong to the same connect component, and these pairs can be enumerated in O(log n) space using standard recursive tree descent.
30
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
