javascriptalgorithmrecursionbinary-tree

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


Solution

  • 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)
    );