{"id":33812,"date":"2024-11-01T09:20:42","date_gmt":"2024-11-01T09:20:42","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33812"},"modified":"2024-11-01T11:46:34","modified_gmt":"2024-11-01T11:46:34","slug":"python-coding-test-course-finding-the-diameter-of-a-tree","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33812\/","title":{"rendered":"Python Coding Test Course, Finding the Diameter of a Tree"},"content":{"rendered":"

<\/p>\n

\n Trees are one of the most important data structures in computer science. In particular, trees are useful for representing hierarchical relationships and are used in various algorithmic problems. This lecture will cover the problem of finding the diameter of a tree.
\n The diameter refers to the longest path between two nodes in the tree. This problem can be solved using DFS (Depth First Search) or BFS (Breadth First Search) algorithms.\n <\/p>\n

Problem Description<\/h2>\n

\n Each node in the given non-empty tree is represented by an integer. Solve the problem of finding the length of the longest path between two nodes in the tree.
\n The input consists of the number of nodes in the tree N<\/code> and N-1<\/code> edge information. The edge information is provided in a way that connects two nodes.
\n Specifically, the input will be given in the following format:\n <\/p>\n

\n    N\n    a1 b1\n    a2 b2\n    ...\n    a(N-1) b(N-1)\n    <\/pre>\n
\n        Here, a<\/code> and b<\/code> represent the two connected nodes, respectively.\n    <\/p>\n
Input Example<\/h2>\n
\n    5\n    1 2\n    1 3\n    2 4\n    2 5\n    <\/pre>\n
Output Example<\/h2>\n
\n    3\n    <\/pre>\n
\n        In this case, the diameter of the tree is between node 4 and node 5, with the path being 4 \u2192 2 \u2192 1 \u2192 3 or 4 \u2192 2 \u2192 5.
\n        Therefore, the output is 3<\/code>.\n    <\/p>\n
Solution<\/h2>\n
\n        To find the diameter of the tree, we can use DFS or BFS algorithms.
\n        The general approach is as follows:\n    <\/p>\n
    \n
  1. \n            In the first step, perform DFS from an arbitrary node to find the farthest node.
    \n            Let’s call this node X<\/code>.\n        <\/li>\n
  2. \n            In the second step, perform DFS again from node X<\/code> to find the farthest node, Y<\/code>.
    \n            The path between X<\/code> and Y<\/code> will be the diameter of the tree.\n        <\/li>\n<\/ol>\n
    \n        Through this process, the time complexity will be O(N)<\/code>, implemented by recursively calling DFS.\n    <\/p>\n
    Python Code Implementation<\/h2>\n
    \n        Now, based on the logic above, let’s implement the code to find the diameter of the tree in Python.
    \n        Check the details of each step with the code provided below.\n    <\/p>\n
    \nfrom collections import defaultdict\n\ndef dfs(graph, node, visited):\n    visited.add(node)\n    max_distance = 0\n    farthest_node = node\n\n    for neighbor in graph[node]:\n        if neighbor not in visited:\n            distance, next_node = dfs(graph, neighbor, visited)\n            distance += 1\n            \n            if distance > max_distance:\n                max_distance = distance\n                farthest_node = next_node\n\n    return max_distance, farthest_node\n\ndef tree_diameter(edges, n):\n    graph = defaultdict(list)\n    \n    for a, b in edges:\n        graph[a].append(b)\n        graph[b].append(a)\n\n    # Step 1: start DFS from an arbitrary node (1)\n    visited = set()\n    _, farthest_node = dfs(graph, 1, visited)\n\n    # Step 2: start DFS from the farthest node found\n    visited.clear()\n    diameter, _ = dfs(graph, farthest_node, visited)\n\n    return diameter\n\n# Input reading part\nn = int(input())\nedges = [tuple(map(int, input().split())) for _ in range(n-1)]\nprint(tree_diameter(edges, n))\n<\/code>\n    <\/pre>\n
    Code Explanation<\/h2>\n
    \n        The above code is structured in the following way:\n    <\/p>\n