2

So I'm working on this problem:

Given the root of a binary tree, return 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.

The length of a path between two nodes is represented by the number of edges between them.

Here's how I tried to solve:

var diameterOfBinaryTree = function(root) {

  if (root === null) return 0;
  let max_height = 0;

  function maxDepth(node) {
    if (node === null) return 0;
    var lh = maxDepth(node.left);
    var rh = maxDepth(node.right);

    return 1 + Math.max(lh, rh);
  }

  max_height = Math.max(max_height, maxDepth(root.left) + maxDepth(root.right));

  diameterOfBinaryTree(root.left);
  diameterOfBinaryTree(root.right);

  return max_height
}

Now, this does work except apparently for the case when the longest path doesn't pass through the root node. But I did try to incorporate those case through, i.e I do iterate on every node of the tree:

diameterOfBinaryTree(root.left);
diameterOfBinaryTree(root.right);

Where am I going wrong? Appreciate any help. Note that I do have to optimize this from O(N2) to O(N) but for now I'm just trying the brute force.

The test case for which it fails is this tree:

enter image description here

Consider the longest path in this passes from -1 to -2

Improve this question
3
  • Can you add an example binary tree for which the longest path doesn't pass through the root, in some reasonable notation? Commented Aug 20, 2024 at 18:55
  • 1
    @PresidentJamesK.Polk Consider this. I'm getting an output 7 whereas it should be 8 (Path between -1 and -2) : [4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2] Here's my submission: leetcode.com/problems/diameter-of-binary-tree/submissions/… Commented Aug 20, 2024 at 18:58
  • 1
    @PresidentJamesK.Polk: Note that this doesn't have to be a balanced binary tree. So imagine a case where one subtree is very short and the other subtree is very tall; you might get a longer path by taking two different branches from the tall subtree (meaning that you don't pass through the root) than by taking one branch from each subtree (meaning that you do). Commented Aug 20, 2024 at 19:16

2 Answers 2

Reset to default
3

But I did try to incorporate those case through, i.e I do iterate on every node of the tree:

diameterOfBinaryTree(root.left);
diameterOfBinaryTree(root.right);

Where am I going wrong?

The diameterOfBinaryTree function performs a computation and returns a value, but it doesn't have any "side effects" — it doesn't actually do anything — so there's never any reason to call it and discard its result. And that's a good thing! Pure functions like this one are easier to reason about (both for humans and for compilers). But it means that these recursive calls are pointless.

Instead, you need to actually use the result:

return Math.max(
    maxDepth(root.left) + maxDepth(root.right),
    diameterOfBinaryTree(root.left),
    diameterOfBinaryTree(root.right)
);
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

Hmm, but I thought I was updating max_height on every call and finally return it. So what was the mistake in that?
@ABGR max_height is local to the function; it's not going to persist across function calls.
Ahh, now I'm a bit confused :) See this: stackoverflow.com/questions/78592674/… Had a similar situation and I got to know that while the local call resets the declared variable each time, the top caller would make it bigger and bigger as the recursion unwinds and that made sense to me. Appreciate your insights and your solution does work perfectly.
Hmm with a bit of thinking it's clear. Thank you. You're right the earlier recursive calls were actually pointless since the max_height would be evaluated on the basis of top call only. Is that correct? So I could make it work this way though even with declaring max_height: max_height = Math.max(max_height, maxDepth(root.left) + maxDepth(root.right), diameterOfBinaryTree(root.left), diameterOfBinaryTree(root.right));
@ABGR: Right -- the let keyword means that a new/separate max_height is created for each call to this function, and these different max_heights don't interfere with each other. The return max_height only returns the max_height from the current call. Re: "I could make it work this way though even with declaring max_height": There's really no reason to do that, but yes: if it's important to you, you can.
-1

You need to begin traversing from the root and then calculate diameter max value of current diameter and addition of left+right on the iteration of the node you are at.

function diameterOfBinaryTree(root) {
    let max_height = 0;
    
    function maxDepth(node) {
        if (!node) return 0;// if our node is falsy, means no path anymore, return 0

        // Assign the left  of tree to leftHeight and right of tree to rightHeight
        const leftHeight = maxDepth(node.left); 
        const rightHeight = maxDepth(node.right);

        // take the max of current diameter and combination of left+right (in case path goes through root)
        max_height = Math.max(diameter, leftHeight + rightHeight);
        return Math.max(leftHeight, rightHeight) + 1; // add 1 to go a level above
    }
    maxDepth(root); // begin traversing from root
    return max_height;
}
Improve this answer

1 Comment

Hmm, I assume you would want let diameter =0 to be declared too besides max_height. Even then this fails for the exact same test case. Besides, I was actually curious why my solution was not working.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.