How would you find the diameter of a binary tree?

The diameter of a binary tree refers to the longest path between any two nodes in a binary tree. This path may or may not pass through the root.

Algorithm to find the diameter of a binary tree:

1. Compute the height (or depth) of the left subtree.

2. Compute the height of the right subtree.

3. Compute the diameter of the left subtree.

4. Compute the diameter of the right subtree.

5. Return the maximum value of the following three:

The diameter of the left subtree.

The diameter of the right subtree.

The sum of the height of the left subtree and the height of the right subtree. (This corresponds to the longest path through the root)

We can implement this algorithm using a simple recursive function in any programming language.

In Python, for example, you might write a function like this:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None


def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))


def diameter(node):
    if node is None:
        return 0

    lheight = height(node.left)
    rheight = height(node.right)

    ldiameter = diameter(node.left)
    rdiameter = diameter(node.right)

    return max(lheight + rheight + 1, max(ldiameter, rdiameter))


# Testing the function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("Diameter of the given binary tree is %d" % (diameter(root)))

The time complexity of the above function is O(N²) and since we’re computing the height in every recursive call, we can optimize the function by calculating the height in the same recursive function where we’re calculating the diameter of the tree.

To implement this, we can make the function to return two values: the height and the diameter of the node as a pair or struct depending on the programming language you’re using.

Here’s how you might change the function in Python:

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def diameter_of_binary_tree(root):
    diameter, _ = get_diameter_and_height(root)
    return diameter

def get_diameter_and_height(node):
    if node is None:
        return 0, 0

    ld, lh = get_diameter_and_height(node.left)
    rd, rh = get_diameter_and_height(node.right)

    return max(lh + rh, ld, rd), 1 + max(lh, rh)

# Testing the function
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

print("Diameter of the binary tree is %d" % (diameter_of_binary_tree(root)))

So there is your optimized Python solution.

The time complexity of this optimized method is O(N), where N is the number of nodes in the binary tree. This is because we’re visiting every node once.

The space complexity is O(log N) for a balanced tree and O(N) in the worst case, due to recursion. This represents the maximum number of concurrent recursive function calls that we have at any one point - i.e., the maximum depth of the recursion.