543. Diameter of Binary Tree

leetcode

Problem:

The problem is to determine the diameter of a binary tree. The diameter of a binary tree is defined as the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Prerequsite

To solve this problem, work on the 104. Maximum Depth of Binary Tree first. Diameter of N-Ary Tree

Solution Description:

To implement the solution, we need to use a recursive Depth-First Search (DFS) approach. The main idea is to calculate the depth of the left subtree and the right subtree for each node, and track the maximum diameter found at each step.

Here's the plan:

Use a helper function to compute the depth of a tree.
Track the maximum diameter using a variable that gets updated while calculating the depth.
For any node, the diameter passing through that node would be the sum of the depth of the left subtree and the depth of the right subtree.
Return the tracked maximum diameter.

The time complexity of this approach is O(n) because each node is visited once. The space complexity is O(h), where h is the height of the tree, due to the recursion stack.

Example:

Consider a binary tree:

The longest path goes from node 4 to node 5 through nodes 2 and 1, so the diameter is 3.

Setup:

We'll define a helper function to recursively calculate the depth of the tree and update the diameter. We'll use modern JavaScript to implement this.

/**
 * Definition for a binary tree node.
 * @param {number} val
 * @param {TreeNode|null} left
 * @param {TreeNode|null} right
 */
function TreeNode(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
}

/**
 * Main solution function to calculate the diameter of binary tree
 * @param {TreeNode} root - root of the binary tree
 * @return {number} - diameter of the tree
 */
function diameterOfBinaryTree(root) {
    const log = typeof NestedInteger !== 'undefined' ? () => {} : console.log;
    const table = typeof NestedInteger !== 'undefined' ? () => {} : console.table;

    let diameter = 0;

    function depth(node) {
        if (node === null) return 0;

        const leftDepth = depth(node.left);
        const rightDepth = depth(node.right);

        diameter = Math.max(diameter, leftDepth + rightDepth);

        return Math.max(leftDepth, rightDepth) + 1;
    }

    depth(root);
    return diameter;
}

// Test cases
const testCases = [
    { root: new TreeNode(1, null, new TreeNode(2)), expected: 1 },
    { root: new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3)), expected: 3 },
    { root: new TreeNode(1, new TreeNode(2)), expected: 1 },
    { root: new TreeNode(1), expected: 0 },
    { root: new TreeNode(1, null, new TreeNode(2, null, new TreeNode(3))), expected: 2 },
    { root: new TreeNode(1, new TreeNode(2, new TreeNode(3, new TreeNode(4, new TreeNode(5))))), expected: 4 },
];

testCases.forEach((test, index) => {
    const result = diameterOfBinaryTree(test.root);
    console.log(`Test Case ${index + 1}: ${result === test.expected ? 'Passed' : 'Failed'} (Expected: ${test.expected}, Got: ${result})`);
});