Java Coding Test Course, Finding the Diameter of a Tree

1. Problem Definition

The problem of finding the diameter of a given tree is an important topic that requires algorithmic thinking.
The diameter of a tree refers to the length of the longest path between two vertices. This can be computed by leveraging the characteristics of the tree structure and serves as the foundation for various application problems.
Therefore, solving this problem is a crucial step to achieving good results in coding tests.

2. Understanding the Problem

A tree is a non-linear data structure composed of nodes, with levels and parent-child relationships. To find the diameter of a tree, we must consider the tree as a type of graph and
use graph traversal algorithms.
The most efficient way to find the diameter is to use two depth-first searches (DFS).

The first DFS starts from an arbitrary node and finds the farthest node. Then, running DFS again from this newly found node will measure the maximum distance, which will be the diameter of the tree.
This approach has a time complexity of O(N), which is very efficient.

3. Problem Solving Strategy

The strategy to solve the problem is as follows:

  1. Construct the Tree: First, create the tree structure based on the given data.
  2. Implement DFS: Implement the depth-first search algorithm to find the farthest node from a specific node.
  3. Calculate the Diameter: Run DFS again from the farthest node found in the first DFS to calculate the diameter.

4. Java Code Implementation


import java.util.*;

class TreeNode {
    int val;
    List children;

    TreeNode(int x) {
        val = x;
        children = new ArrayList<>();
    }
}

public class DiameterOfTree {

    private int maxDiameter = 0;

    public int getTreeDiameter(TreeNode root) {
        if (root == null) return 0;
        dfs(root);
        return maxDiameter;
    }

    private int dfs(TreeNode node) {
        if (node == null) return 0;

        int firstMax = 0; 
        int secondMax = 0;

        for (TreeNode child : node.children) {
            int childDepth = dfs(child);
            if (childDepth > firstMax) {
                secondMax = firstMax;
                firstMax = childDepth;
            } else if (childDepth > secondMax) {
                secondMax = childDepth;
            }
        }

        maxDiameter = Math.max(maxDiameter, firstMax + secondMax);
        return firstMax + 1;
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);

        root.children.add(node2);
        root.children.add(node3);
        node2.children.add(node4);
        node2.children.add(node5);

        DiameterOfTree diameter = new DiameterOfTree();
        int result = diameter.getTreeDiameter(root);
        System.out.println("Diameter of the tree: " + result);
    }
}

The code above defines the TreeNode class and creates a tree that connects each node.
The main method sets up the tree and calculates the diameter via the getTreeDiameter method.

5. Code Explanation

In this section, we will explain the key parts of the code.

TreeNode Class

The TreeNode class represents each node of the tree and includes the value of the node and a list of child nodes.
The constructor initializes the value and an empty list of children.

DFS Using the Diameter Variable

The DFS explores each node to determine the depths of child nodes and to find the maximum depth.
At the same time, when calculating the maximum diameter, it uses two maximum depths to update the diameter.
This depth value is returned plus one when returning to the parent node.

6. Performance Analysis

The implementation above has a time complexity of O(N), where N is the number of nodes.
Since each node is visited once, it is highly efficient.
The space complexity is also O(H), where H is the height of the tree.
This performance is expected to be very good even for actual large-scale data.

7. Various Test Cases

The algorithm can be validated through test cases with various tree structures.
For example, consider the following tree structures:

  • Single-node tree
  • Spanning tree where all nodes are connected in series
  • Balanced tree
  • Unbalanced tree

By validating whether the diameter is correctly calculated for each structure, we can enhance the reliability of the algorithm.

8. Conclusion

The problem of finding the diameter of a tree is very important for understanding fundamental concepts of algorithms and strengthening efficient problem-solving abilities using DFS.
The methods presented can provide a foundation for solving many coding test problems.
Remember that this methodology using the Java language can be applied in various situations, and I hope it helps in solving different problems.