Question on interview: diameter of binary tree.

I got a task on interview to calculate diameter of given binary tree.
While I don’t like to solve abstract problems ( I have a lot of problems to solve in my projects already) I’ve found this one particularly interesting as it actually has practical value in one of algorithms on DOM tree (that is non-binary tree but still). So I’ve decided to investigate it.

Let’s define the problem this way:
The diameter (or width) of binary tree is the number of tree edges on the longest path between two leaves in the tree.
The task is to write function that returns the width for any given binary tree.

Nodes in a tree are defined as {left:nodeOrNull,right:nodeOrNull} (I am using JavaScript here for brevity).
The function looks like this:
function treeWidth(treeRootNode) {} // returns max distance found in the tree.

So for the tree:

      a
     / \
    b   c
       / \
      d   e
           \
            f

the function shall return 4 as longest path is b-a-c-e-f

I shall admit that I’ve spent something around one hour to find the solution. Good this timing or bad – I don’t know, programming is not a sport really. I did it at the end and that’s enough. The algorithm has computational complexity of O(N) as each node of the tree is visited exactly once. Memory consumption is expressed as O(h) where h is max depth of the tree.

If you want you can test yourself finding the solution, mine is under the cut below.

The function itself: (Note I didn’t do some obvious code minifications here).

    function treeWidth(tree)
    {
      var max_width = 0;
      function max(n1, n2) { return n1 > n2? n1:n2; }
          
      function maxDepth( node, nodeDepth ) 
      {
        if( node.left && node.right )
        {
          var l = maxDepth(node.left,1);
          var r = maxDepth(node.right,1);
          var width = l + r;
          max_width = max(width,max_width);
          return nodeDepth + max(l,r);
        }
        else if( node.left )
        {
          var r = nodeDepth + maxDepth(node.left,1);
          max_width = max(r,max_width);
          return r;
        }
        else if( node.right )
        {
          var r = nodeDepth + maxDepth(node.right,1);
          max_width = max(r,max_width);
          return r;
        }
        return nodeDepth;
      }
      maxDepth(tree,0);
      return max_width;
   }

And here are test cases:

   function assert(exp, msg) { if(!exp) throw msg + " case failed"; }
   
   
//      a
//     / \
//    b   c
//       / \
//      d   e
//           \
//            f

//  widest path here is b-a-c-e-f = 4

  function produceTree1()
  {
    var f = {left:null,right:null,val:"f"};
    var e = {left:null,right:f,val:"e"};
    var d = {left:null,right:null,val:"d"};
    var c = {left:d,right:e,val:"c"};
    var b = {left:null,right:null,val:"b"};
    return  {left:b, right:c, val:"a" };
  }
  
  assert( 4 == treeWidth(produceTree1()), "tree1" );
    

//      a
//     / \
//    b   c
//       / \
//      d   e
//     /     \
//    g       f
//   /         \
//  h           i

//  widest path here is h-g-d-c-e-f-i = 6

  function produceTree2()
  {
    var h = {left:null,right:null,val:"h"};
    var i = {left:null,right:null,val:"i"};
    var g = {left:h,right:null,val:"g"};
    var f = {left:null,right:i,val:"f"};
    var d = {left:g,right:null,val:"d"};
    var e = {left:null,right:f,val:"e"};
    var c = {left:d,right:e,val:"c"};
    var b = {left:null,right:null,val:"b"};
    return  {left:b, right:c, val:"a" };
  }
  
  assert( 6 == treeWidth(produceTree2()), "tree2" );

// degenerate case:
//   
//      a
//       \
//        b
//         \
//          c
//           \
//            d
//             \
//              e

//  widest path here is a-b-c-d-e = 4

  function produceTree3()
  {
    var e = {left:null,right:null,val:"e"};
    var d = {left:null,right:e,val:"d"};
    var c = {left:null,right:d,val:"c"};
    var b = {left:null,right:c,val:"b"};
    return  {left:null,right:b, val:"a" };
  }

  assert( 4 == treeWidth(produceTree3()), "tree3" );
  
  console.log("all tests are passed");