Diameter of a binary tree - returning an array

Question

I get that the idea is to traverse from each end node, find the larger height of left and right, and add them to find the biggest diameter. In most solutions, they're using max[0] as arg and return that as well. I tried a different approach, but somehow it passed all tests except the one that has the biggest diameter without passing through the root. What went wrong here?

var diameterOfBinaryTree = function(root) {
    const result = dfs(root, 0);
    return result[1];
};

function dfs(root, max) {
    if (!root) return [0, max];
    const left = dfs(root.left, max);
    const right = dfs(root.right, max);

    const height = 1 + Math.max(left[0], right[0]);
    max = Math.max(max, left[0] + right[0]);

    return [height, max];
}

Btw, no reason to pass in `max` as a parameter - the argument value is always `0`. — Bergi, Feb 04 '23 at 23:49
@Bergi but where would i use left[1]/right[1]? in the dfs function max is constantly updated regardless of whether they belong to left or right — tommy-ling, Feb 05 '23 at 00:05
"*max is constantly updated*" - no it is not. [Each call has its own variable](https://stackoverflow.com/q/518000/1048572) (that is initially `0` and then set to `left[0] + right[0]`), it's not shared. — Bergi, Feb 05 '23 at 00:10

score 0 · Accepted Answer · answered Feb 05 '23 at 00:57

You're looking for

function diameterOfBinaryTree(root) {
    return dfs(root).diameter;
}

function dfs(node) {
    if (!node) return {height: 0, diameter: 0};
    const left = dfs(node.left);
    const right = dfs(node.right);

    const height = 1 + Math.max(left.height, right.height);
    const diameter = Math.max(left.height + right.height, left.diameter, right.diameter);

    return {height, diameter};
}

Diameter of a binary tree - returning an array

1 Answers1