\n 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.
\n 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).
\n In this course, we will explore how to find the diameter of a tree and how to implement it using JavaScript.\n <\/p>\n
\n 7\n 1 2 3\n 1 3 4\n 2 4 3\n 2 5 2\n 3 6 1\n 3 7 3\n <\/pre>\nOutput<\/h3>\n
7<\/pre>\n<\/div>\n3. Problem Approach<\/h2>\n
\n One way to find the diameter of a tree is to use two rounds of DFS or BFS as follows:\n <\/p>\n
\n
- Start from a random node and find the most distant node. We will call this node a temporary node<\/strong>.<\/li>\n
- 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.<\/li>\n<\/ol>\n
4. JavaScript Implementation<\/h2>\n
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.<\/p>\n
\n class TreeNode {\n constructor(value) {\n this.value = value;\n this.children = [];\n }\n }\n\n class Tree {\n constructor() {\n this.root = null;\n }\n\n addEdge(parentValue, childValue) {\n const parentNode = this.findNode(this.root, parentValue);\n const childNode = new TreeNode(childValue);\n if (parentNode) {\n parentNode.children.push(childNode);\n } else {\n this.root = parentNode; \/\/ If root is null, set it as the first node\n }\n }\n\n findNode(node, value) {\n if (!node) return null;\n if (node.value === value) return node;\n for (const child of node.children) {\n const result = this.findNode(child, value);\n if (result) return result;\n }\n return null;\n }\n\n diameter() {\n return this.diameterHelper(this.root).diameter;\n }\n\n diameterHelper(node) {\n if (!node) return { height: 0, diameter: 0 };\n\n let maxHeight1 = 0, maxHeight2 = 0, diameter = 0;\n\n for (const child of node.children) {\n const { height, diameter: childDiameter } = this.diameterHelper(child);\n diameter = Math.max(diameter, childDiameter);\n if (height > maxHeight1) {\n maxHeight2 = maxHeight1;\n maxHeight1 = height;\n } else if (height > maxHeight2) {\n maxHeight2 = height;\n }\n }\n\n diameter = Math.max(diameter, maxHeight1 + maxHeight2);\n return { height: maxHeight1 + 1, diameter };\n }\n }\n <\/code><\/pre>\n5. Code Explanation<\/h2>\n
The code above includes the functionality to find the diameter of a tree. Let\u2019s explain the main parts.<\/p>\n
\n
- TreeNode Class:<\/strong> Represents each node of the tree. It includes the node value and a list of the node’s children.<\/li>\n
- Tree Class:<\/strong> This class manages the tree. It includes the
addEdge<\/code> method to add child nodes and thefindNode<\/code> method to find a node with a given value.<\/li>\n- diameter Method:<\/strong> Calls the
diameterHelper<\/code> function to calculate the tree’s diameter.<\/li>\n- diameterHelper Function:<\/strong> Recursively computes the maximum height at each node and updates the diameter at the current node.<\/li>\n<\/ul>\n
6. Performance Analysis<\/h2>\n