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.”