Solving Diameter of Binary Tree in Python: Step-by-Step Guide

The Diameter of a Binary Tree is one of the most frequently asked problems in coding interviews and a fundamental exercise for understanding tree traversal and recursion. In this tutorial, we will break down what the diameter is, why it matters, how to compute it efficiently in Python, and the best practices you should follow when implementing the solution.

What Is the Diameter of a Binary Tree?

The diameter (also called the width) of a binary tree is defined as the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. The length of the path is measured by the number of edges between the nodes, not the number of nodes themselves.

For example, consider the following binary tree:

The longest path here is between node 6 and node 3, passing through nodes 4 -> 2 -> 1 -> 3. This path contains 4 edges, so the diameter is 4.

Why It Matters

Understanding how to compute the diameter of a binary tree is important for several reasons:

Interview relevance: It is a classic problem that tests your understanding of recursion, tree traversal, and algorithmic optimization.
Real-world applications: Tree diameter concepts appear in network topology analysis, organizational hierarchy depth, and routing problems.
Algorithmic thinking: It teaches you how to combine local computation (height of a subtree) with global state tracking (the maximum diameter found so far).
Foundation for advanced topics: The same pattern of "compute something locally, update a global answer" appears in many harder tree and graph problems.

Defining the Tree Node

Before solving the problem, we need a class to represent a binary tree node. In Python, this is typically done using a simple class with val, left, and right attributes.

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

This definition allows us to construct any binary tree by linking nodes together through their left and right pointers.

The Naive Approach

A straightforward way to compute the diameter is to, for every node, calculate the height of its left and right subtrees and sum them. The diameter is the maximum such sum across all nodes.

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

def diameter_naive(root):
    if root is None:
        return 0

    # Diameter passing through the current node
    left_height = height(root.left)
    right_height = height(root.right)
    through_root = left_height + right_height

    # Diameter entirely within left or right subtree
    left_diameter = diameter_naive(root.left)
    right_diameter = diameter_naive(root.right)

    return max(through_root, left_diameter, right_diameter)

While correct, this approach has a major flaw: the height function is called for every node, leading to repeated work. The time complexity becomes O(n²) in the worst case (for a skewed tree), which is inefficient for large inputs.

The Optimal Approach: Depth-First Search

The key insight is that we can compute the height of each subtree once while simultaneously updating the maximum diameter found so far. This reduces the time complexity to O(n), where n is the number of nodes in the tree.

The strategy is:

Perform a post-order traversal (process children before the parent).
For each node, compute the height of its left and right subtrees.
The candidate diameter at that node is left_height + right_height.
Update a global (or nonlocal) variable that tracks the maximum diameter.
Return the height of the current node to its parent.

Here is the complete implementation:

class Solution:
    def diameterOfBinaryTree(self, root):
        self.diameter = 0

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

            left_height = dfs(node.left)
            right_height = dfs(node.right)

            # Update the diameter: longest path through this node
            self.diameter = max(self.diameter, left_height + right_height)

            # Return the height of this node
            return 1 + max(left_height, right_height)

        dfs(root)
        return self.diameter

Notice that we use self.diameter to maintain state across recursive calls. This is a clean way to track the maximum without returning multiple values from the recursive function.

Step-by-Step Walkthrough

Let us trace the algorithm on the example tree from earlier:

The DFS traversal visits nodes in this order: 6 -> 4 -> 5 -> 2 -> 3 -> 1. At each node, we compute the height and update the diameter:

Node 6: left = 0, right = 0, diameter candidate = 0, returns height 1.
Node 4: left = 1 (from node 6), right = 0, diameter candidate = 1, returns height 2.
Node 5: left = 0, right = 0, diameter candidate = 0, returns height 1.
Node 2: left = 2 (from node 4), right = 1 (from node 5), diameter candidate = 3, returns height 3.
Node 3: left = 0, right = 0, diameter candidate = 0, returns height 1.
Node 1: left = 3 (from node 2), right = 1 (from node 3), diameter candidate = 4, returns height 4.

The maximum diameter encountered is 4, which is the correct answer.

Testing the Solution

To verify our solution, let us build the tree and run the function:

# Construct the tree
#         1
#        / \
#       2   3
#      / \
#     4   5
#    /
#   6

root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.left.left.left = TreeNode(6)

solution = Solution()
print(solution.diameterOfBinaryTree(root))  # Output: 4

You can also test edge cases:

# Empty tree
print(solution.diameterOfBinaryTree(None))  # Output: 0

# Single node
single = TreeNode(1)
print(solution.diameterOfBinaryTree(single))  # Output: 0

# Skewed tree (linked list shape)
skewed = TreeNode(1)
skewed.right = TreeNode(2)
skewed.right.right = TreeNode(3)
print(solution.diameterOfBinaryTree(skewed))  # Output: 2

Alternative Implementation Without Instance Variables

If you prefer not to use instance variables, you can return both the height and the current diameter from the recursive function. This is a more functional style:

def diameterOfBinaryTree(root):
    def dfs(node):
        if node is None:
            return 0, 0  # height, diameter

        left_height, left_diameter = dfs(node.left)
        right_height, right_diameter = dfs(node.right)

        current_height = 1 + max(left_height, right_height)
        current_diameter = max(
            left_height + right_height,
            left_diameter,
            right_diameter
        )

        return current_height, current_diameter

    _, diameter = dfs(root)
    return diameter

This version is equally efficient and avoids mutable shared state, which some developers find cleaner.

Best Practices

When implementing the diameter of a binary tree, keep the following best practices in mind:

Use the O(n) DFS approach: Always prefer the single-pass DFS solution over the naive O(n²) approach, especially for large trees.
Handle edge cases explicitly: Make sure your code handles empty trees, single-node trees, and skewed trees correctly.
Clarify the definition: Some problem statements define diameter by the number of edges, others by the number of nodes. Always confirm which definition is expected before coding.
Avoid global mutable state when possible: If you use a class-level or instance-level variable, make sure it is reset between calls, or use the functional approach that returns tuples.
Write tests: Test with balanced trees, skewed trees, and degenerate cases to ensure correctness.
Watch recursion depth: For very deep trees, Python's default recursion limit (usually 1000) may be exceeded. In such cases, consider an iterative post-order traversal using an explicit stack.

Iterative Approach for Deep Trees

If recursion depth is a concern, you can implement the same logic iteratively using a stack. Here is an example:

def diameterOfBinaryTree_iterative(root):
    if root is None:
        return 0

    stack = [root]
    heights = {}
    diameter = 0

    # Post-order traversal using a stack
    while stack:
        node = stack[-1]
        if node.left and node.left not in heights:
            stack.append(node.left)
        elif node.right and node.right not in heights:
            stack.append(node.right)
        else:
            stack.pop()
            left_h = heights.get(node.left, 0)
            right_h = heights.get(node.right, 0)
            heights[node] = 1 + max(left_h, right_h)
            diameter = max(diameter, left_h + right_h)

    return diameter

This iterative version avoids recursion entirely and is suitable for extremely deep trees where the recursive solution would fail.

Complexity Analysis

For the optimal DFS solution:

Time complexity: O(n), because each node is visited exactly once.
Space complexity: O(h), where h is the height of the tree. This accounts for the recursion stack. In the worst case (skewed tree), this is O(n); in a balanced tree, it is O(log n).

The iterative version has the same time complexity but uses an explicit stack and a dictionary, which may use more memory in practice due to the dictionary overhead.

Conclusion

The diameter of a binary tree is a deceptively simple problem that rewards a deep understanding of recursion and tree traversal. By combining the computation of subtree heights with the tracking of a global maximum, you can solve the problem efficiently in O(n) time with clean, readable code. Whether you choose the recursive approach with instance variables, the functional tuple-returning style, or the iterative stack-based method, the core idea remains the same: compute heights bottom-up and update the diameter at every node. Mastering this pattern will not only help you ace interviews but also build a strong foundation for tackling more complex tree and graph problems in the future.