Count cycle in binary tree

Question

Count the number of cycle in the given binary tree.

Codemia · Accepted Answer

To count the number of cycles in a binary tree, we first need to understand what constitutes a cycle. In a binary tree, a cycle occurs when a node's child points back to one of its ancestors, forming a loop. This problem can be treated like a graph traversal problem where we need to detect cycles in a directed graph. The appropriate approach for this is Depth-First Search (DFS), which allows us to explore each node and keep track of visited nodes. A cycle can be detected if we revisit a node that is already in our current path of exploration.

1. **Initialization**: Create a set to keep track of visited nodes and a stack to track the current path of exploration.
2. **DFS Function**: Implement a recursive DFS function that:
   - Marks the current node as visited.
   - Adds the current node to the current path.
   - Iterates over each child of the current node:
     - If the child is already in the current path, a cycle is detected and we increment the cycle count.
     - If the child hasn't been visited yet, recursively call DFS on the child.
   - After exploring all children, remove the current node from the current path.
3. **Count Cycles**: Call the DFS function for each unvisited node in the tree.

**Example**: For a tree structured as follows:
```
      A
     / \
    B   C
   / \
  D   E
   \  / 
    F
     |
     B (Cycle)
```
Starting the DFS from node A, we will explore B -> D -> F -> B, detecting a cycle.

The following is the Python implementation of the above algorithm:
```python
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

class CycleCounter:
    def __init__(self):
        self.cycle_count = 0

def count_cycles(self, root):
        visited = set()
        self.dfs(root, visited, set())
        return self.cycle_count

def dfs(self, node, visited, current_path):
        if node is None:
            return
        if node in current_path:
            self.cycle_count += 1
            return
        if node in visited:
            return

visited.add(node)
        current_path.add(node)

for child in node.children:
            self.dfs(child, visited, current_path)

current_path.remove(node)
```
This code defines a `TreeNode` class and a `CycleCounter` class, implementing the DFS cycle detection method.

The time complexity of this solution is O(N), where N is the number of nodes in the binary tree. This is because, in the worst case, we might visit every node once. The space complexity is O(H) for the recursion stack, where H is the height of the tree. In a balanced binary tree, this would be O(log N), but in the worst case (a skewed tree), it could be O(N). Additionally, we use O(N) space for the visited set.

1. **Empty Tree**: If the tree has no nodes, the cycle count should be 0.
2. **Single Node**: A single node pointing to itself (self-loop) should count as 1 cycle.
3. **Deeply Nested Nodes**: A long chain of nodes without cycles should correctly return 0.
4. **Multiple Cycles**: The implementation should correctly count multiple cycles without double counting.
5. **Disconnected Components**: If the tree consists of separate components, the algorithm should still correctly identify cycles in each component.

Count cycle in binary tree

Brex

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

Brex Software 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