LeetCode 1245: Tree Diameter Solution

Master LeetCode problem 1245 (Tree Diameter), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1245. Tree Diameter

Medium

Tree Depth-First Search Breadth-First Search Graph Topological Sort

Problem Explanation

Explanation

To find the diameter of a tree, we need to find the longest path between any two nodes in the tree. We can solve this problem using Depth-First Search (DFS). The idea is to perform two DFS traversals. First, we start from an arbitrary node and find the farthest node from it. Then, we start from that farthest node and find the farthest node from it. The distance between these two farthest nodes will be the diameter of the tree.

Perform a DFS traversal starting from an arbitrary node to find the farthest node (let's call it node1) from it.
Perform another DFS traversal starting from node1 to find the farthest node (let's call it node2) from it.
The distance between node1 and node2 will be the diameter of the tree.

Time complexity: O(N) - We visit each node once during the two DFS traversals. Space complexity: O(N) - We use recursive stack space for DFS.

Solution Code

class Solution {
    public int treeDiameter(int[][] edges) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
            graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
        }
        
        int[] farthest = findFarthestNode(graph, 0);
        farthest = findFarthestNode(graph, farthest[0]);
        
        return farthest[1];
    }
    
    private int[] findFarthestNode(Map<Integer, List<Integer>> graph, int start) {
        boolean[] visited = new boolean[graph.size()];
        int[] farthest = new int[] {start, 0};
        dfs(graph, visited, start, 0, farthest);
        return farthest;
    }
    
    private void dfs(Map<Integer, List<Integer>> graph, boolean[] visited, int node, int distance, int[] farthest) {
        visited[node] = true;
        if (distance > farthest[1]) {
            farthest[0] = node;
            farthest[1] = distance;
        }
        
        for (int neighbor : graph.getOrDefault(node, new ArrayList<>())) {
            if (!visited[neighbor]) {
                dfs(graph, visited, neighbor, distance + 1, farthest);
            }
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1245 (Tree Diameter)?

This page provides optimized solutions for LeetCode problem 1245 (Tree Diameter) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1245 (Tree Diameter)?

The time complexity for LeetCode 1245 (Tree Diameter) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1245 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1245 in Java, C++, or Python.

Back to LeetCode Solutions