Question 403106 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Diameter of a binary tree – failing case when the longest path doesn't pass through the root

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

Tags:

2

Answers


  1. 0

    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;
}
    Login or Signup to reply.
  2. 0

    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)
);
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search