JavaScript Coding Test Course, Finding the Diameter of a Tree

1. Problem Description

The diameter of a tree refers to the length of the longest path in the tree. A single tree is a connected set of nodes, with each node branching out from a root node.
The problem of finding the diameter of a tree frequently appears in graph theory and is primarily solved using Depth First Search (DFS) or Breadth First Search (BFS).
In this course, we will explore how to find the diameter of a tree and how to implement it using JavaScript.

2. Example Input and Output

Input

        7
        1 2 3
        1 3 4
        2 4 3
        2 5 2
        3 6 1
        3 7 3

Output

7

3. Problem Approach

One way to find the diameter of a tree is to use two rounds of DFS or BFS as follows:

  1. Start from a random node and find the most distant node. We will call this node a temporary node.
  2. Starting from the temporary node, perform DFS or BFS again to find the distance to the furthest node. This distance is the diameter of the tree.

4. JavaScript Implementation

Now, let’s write the code to find the diameter of the tree in JavaScript using the above method. Before we begin, we need to define a simple data structure.


    class TreeNode {
        constructor(value) {
            this.value = value;
            this.children = [];
        }
    }

    class Tree {
        constructor() {
            this.root = null;
        }

        addEdge(parentValue, childValue) {
            const parentNode = this.findNode(this.root, parentValue);
            const childNode = new TreeNode(childValue);
            if (parentNode) {
                parentNode.children.push(childNode);
            } else {
                this.root = parentNode; // If root is null, set it as the first node
            }
        }

        findNode(node, value) {
            if (!node) return null;
            if (node.value === value) return node;
            for (const child of node.children) {
                const result = this.findNode(child, value);
                if (result) return result;
            }
            return null;
        }

        diameter() {
            return this.diameterHelper(this.root).diameter;
        }

        diameterHelper(node) {
            if (!node) return { height: 0, diameter: 0 };

            let maxHeight1 = 0, maxHeight2 = 0, diameter = 0;

            for (const child of node.children) {
                const { height, diameter: childDiameter } = this.diameterHelper(child);
                diameter = Math.max(diameter, childDiameter);
                if (height > maxHeight1) {
                    maxHeight2 = maxHeight1;
                    maxHeight1 = height;
                } else if (height > maxHeight2) {
                    maxHeight2 = height;
                }
            }

            diameter = Math.max(diameter, maxHeight1 + maxHeight2);
            return { height: maxHeight1 + 1, diameter };
        }
    }

5. Code Explanation

The code above includes the functionality to find the diameter of a tree. Let’s explain the main parts.

  • TreeNode Class: Represents each node of the tree. It includes the node value and a list of the node’s children.
  • Tree Class: This class manages the tree. It includes the addEdge method to add child nodes and the findNode method to find a node with a given value.
  • diameter Method: Calls the diameterHelper function to calculate the tree’s diameter.
  • diameterHelper Function: Recursively computes the maximum height at each node and updates the diameter at the current node.

6. Performance Analysis

The time complexity of this algorithm is O(n) as it visits every node in the tree once.
The space complexity is O(h) in the worst case because stack frames are used up to the maximum height of the tree, where h signifies the height of the tree.

7. Conclusion

We have explored how to find the diameter of a tree using JavaScript. Problems of this type frequently appear in coding tests, so
it is beneficial to practice many example problems to become familiar with them.
Understanding and utilizing tree structures and DFS/BFS search methods is important, and these fundamental concepts can be applied in various contexts.