Introduction

In programming and system design, understanding the relationship between graphs and trees can be a game-changer.

Trees are special forms of graphs — but not all graphs are trees! In this blog, we'll explore how to convert between graphs and trees, with Kotlin code snippets to make it all real.

Graph vs Tree — What's the Deal?

  1. A Graph is a collection of nodes (vertices) connected by edges. It can have cycles and can be directed or undirected.

2. A Tree is a connected acyclic graph — no cycles, exactly one path between any two nodes.

3. Every tree is a graph, but not every graph is a tree.

Example

Given a graph like this:

1 - 2
|   |
3 - 4

This graph has cycles. But we can convert it into a tree by removing the edge 2-4 or 3-4, and picking a root, say 1.

Graph to Tree Conversion (in Kotlin)

Here's a basic way to convert a connected undirected graph to a tree using DFS.

We assume the graph is connected and has no self-loops.

fun buildTreeFromGraph(
    graph: Map<Int, List<Int>>,
    root: Int
): Map<Int, List<Int>> {
    val tree = mutableMapOf<Int, MutableList<Int>>()
    val visited = mutableSetOf<Int>()

    fun dfs(current: Int, parent: Int?) {
        visited.add(current)
        tree[current] = mutableListOf()
        
        for (neighbor in graph[current] ?: emptyList()) {
            if (neighbor != parent && !visited.contains(neighbor)) {
                tree[current]?.add(neighbor)
                dfs(neighbor, current)
            }
        }
    }

    dfs(root, null)
    return tree
}

Example

val graph = mapOf(
    1 to listOf(2, 3),
    2 to listOf(1, 4),
    3 to listOf(1),
    4 to listOf(2)
)

val tree = buildTreeFromGraph(graph, 1)
println(tree)
// Output: {1=[2, 3], 2=[4], 3=[], 4=[]}

Key Tips

  1. Start with a root: Always define a starting point when converting a graph to a tree.
  2. Avoid cycles: Keep track of visited nodes to prevent looping.
  3. Handle disconnected graphs: Not all graphs are trees; convert components separately.
  4. Use DFS or BFS: Either traversal works, but DFS is cleaner for recursion.
  5. Parent tracking is essential: To avoid backtracking to the parent node in undirected graphs.

Related LeetCode / DSA Questions

  1. Convert Graph to Tree (conceptual)
  2. Find Tree Diameter
  3. Clone Graph
  4. Minimum Spanning Tree
  5. LCA in Tree

Final Thoughts

  1. Graph and Tree conversions help in many real-world systems like file structures, org charts, and network hierarchies.

2. Think in terms of connectivity and hierarchy when working with trees.

3. Mastering these conversions deepens your understanding of both data structures — and helps in interviews big time!

Call of action

Ready to level up? Click "Call of Action" and start practicing with purpose today.

None