543. Diameter of Binary Tree

#tree #javascript #algorithms #leetcode

Description:

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

Solution:

Time Complexity : O(n)
Space Complexity: O(n)

// Depth first search approach
var diameterOfBinaryTree = function(root) {
    let diameter = 0;
    dfs(root);
    return diameter;

    function dfs(node) {
        if (!node) return 0;

        const left = dfs(node.left);
        const right = dfs(node.right);

        // update diameter at every node
        diameter = Math.max(diameter, left + right);

        // update the max path of the current node
        // 1 is the height of the node itself + longest path of children
        return 1 + Math.max(left, right);
    } 
};