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.

Continue reading “Question on interview: diameter of binary tree.”

boost.coroutine vs my $generator.

Today I saw discussion about boost.coroutine on gmane:

Generators and coroutines are conceptually the same feature and I have implementation of $generator thing that can be used to implement coroutines.

My implementation is of 15 lines of code and does not require any threads/fibers and so context switches – pure C++ with macro magic, pretty straightforward though.

Anyway, here is an example how coroutine can be implemented using that $generator thing.
First, let’s define coroutine (or generator) that will establish connection with some server and will supply (yield) data chunks read from socket:

$generator(net_reader)
{
   socket_t     sock;
   byte         buffer[2048];

   net_reader(const char* addr) { sock.connect(addr); }
   
   // from $emit to $stop is a body of our coroutine:
    
   $emit(slice<byte>) // Coroutine will emit slice<byte> values. Start of coroutine body.

      while( sock.valid() )
      {
          slice<byte> r(buffer,0);
          r.length = sock.read(buffer,sizeof(buffer));
          if(r.length)
            $yield( r ); 
          else 
            break; 
      }

   $stop; // stop. End of coroutine body.
};

Having this we can write code that will read data chunk by chunk and store it in some array.


array<byte> data;
net_reader  get("data.example.com:4002");

for(slice<byte> chunk; get(chunk);)
  data.push(chunk);

That’s easy, no?

Yes, $generator thing is not free from problems (e.g. you cannot use switch() inside its body) but other than that and in 99% of coroutine cases you will get what is needed from generators/coroutines. And without those tons of code.