Find cycle in binary tree

Question

Given a binary tree, determine if it contains a cycle. A cycle occurs when a node can be reached again by following the left and right child pointers. Your solution should return a boolean value: true if a cycle exists, and false otherwise.

Codemia · Accepted Answer

The problem requires determining if a binary tree contains a cycle, which means that there exists at least one node that can be revisited by following the left and right child pointers. This is similar to detecting a cycle in a graph, as a binary tree can be represented as a directed graph where each node points to its children. A Depth-First Search (DFS) approach is suitable here because it allows us to traverse the tree while keeping track of visited nodes. The key challenge is managing the traversal to avoid infinite loops caused by cycles.

1. Utilize DFS to traverse the tree. Start from the root node and explore each node recursively.  
2. Maintain a set to track visited nodes. If a node is revisited during the traversal, it indicates a cycle.  
3. For each node, check if it has already been visited. If it has, return `True`.  
4. If it hasn't, mark it as visited and continue DFS on its left and right children.  
5. If the entire tree is traversed without revisiting any node, return `False`.  
For example, in a tree structure where nodes A, B, and C are connected (A -> B, B -> C, C -> A), DFS would revisit node A when it reaches C, thus confirming a cycle.

Here’s the Python code for the solution:
```python
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def has_cycle(root):
    visited = set()  
    def dfs(node):
        if not node:
            return False  
        if id(node) in visited:
            return True  
        visited.add(id(node))  
        return dfs(node.left) or dfs(node.right)  
    return dfs(root)
```
In this code, we define a `TreeNode` class for the binary tree structure and a `has_cycle` function that utilizes a nested `dfs` function for depth-first traversal.

The time complexity of this solution is O(N), where N is the number of nodes in the binary tree, as we may need to visit each node once during the DFS traversal. The space complexity is also O(N) in the worst case due to the storage of visited nodes in a set, particularly in cases where the tree is skewed and resembles a linked list. In a balanced binary tree, the space complexity can be O(H), where H is the height of the tree, due to the recursion stack.

1. **Empty Tree**: If the tree is empty (root is None), the function should return `False`, as there are no nodes to form a cycle.  
2. **Single Node with Self-Loop**: If a single node points to itself (e.g., `node.left = node`), this should return `True` as it forms a cycle.  
3. **Large Tree with No Cycles**: A large binary tree structured without cycles should return `False`, testing the performance of the solution.  
4. **Deeply Nested Nodes**: A tree where one branch is much deeper than others (e.g., a linked-list-like structure) should also return `False`, ensuring that depth doesn’t incorrectly suggest a cycle.

Find cycle in binary tree

Stripe

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Stripe Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string