Binary Tree Diameter in Python (Time Complexity: O(n))

Given the root of a binary tree, return the length of the diameter of the tree.

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

The length of a path between two nodes is represented by the number of edges between them.

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2:

Input: root = [1,2]
Output: 1

Constraints:

The number of nodes in the tree is in the range [1, 10⁴].
-100 <= Node.val <= 100

Understanding the Problem

The core challenge of this problem is to find the longest path between any two nodes in a binary tree. This path does not necessarily have to pass through the root. The significance of this problem lies in its applications in network design, biological tree structures, and more. A common pitfall is to assume the path must pass through the root, which is not the case.

Approach

To solve this problem, we need to consider the following:

We need to calculate the height of the left and right subtrees for each node.
The diameter at any node will be the sum of the heights of the left and right subtrees.
We need to keep track of the maximum diameter found during the traversal of the tree.

Let's start with a naive approach:

Naive Approach

The naive approach involves calculating the height of the left and right subtrees for each node separately, which leads to a time complexity of O(n^2). This is not optimal for large trees.

Optimized Approach

We can optimize this by using a single traversal of the tree (Depth-First Search). During the traversal, we calculate the height of the subtrees and update the diameter simultaneously. This reduces the time complexity to O(n).

Algorithm

Here is a step-by-step breakdown of the optimized algorithm:

Define a helper function that calculates the height of a subtree and updates the diameter.
Initialize a variable to keep track of the maximum diameter.
Traverse the tree using Depth-First Search.
For each node, calculate the height of its left and right subtrees.
Update the diameter if the sum of the heights of the left and right subtrees is greater than the current diameter.
Return the maximum diameter found.

Code Implementation

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

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        self.diameter = 0

        def height(node):
            if not node:
                return 0
            # Recursively find the height of the left and right subtrees
            left_height = height(node.left)
            right_height = height(node.right)
            # Update the diameter if the path through the current node is longer
            self.diameter = max(self.diameter, left_height + right_height)
            # Return the height of the current node
            return max(left_height, right_height) + 1

        height(root)
        return self.diameter

Complexity Analysis

The time complexity of the optimized approach is O(n), where n is the number of nodes in the tree. This is because we traverse each node exactly once. The space complexity is O(h), where h is the height of the tree, due to the recursion stack.

Edge Cases

Consider the following edge cases:

A tree with only one node. The diameter is 0.
A tree where all nodes are on one side (left or right). The diameter is the height of the tree minus one.

Testing

To test the solution comprehensively, consider the following test cases:

A balanced tree with multiple levels.
A tree with only left children.
A tree with only right children.
A tree with a mix of left and right children.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

Break down the problem into smaller subproblems.
Think about how to use recursion effectively.
Consider edge cases and how your solution handles them.
Practice similar problems to improve your problem-solving skills.

Conclusion

In this blog post, we discussed how to find the diameter of a binary tree using an optimized approach with a time complexity of O(n). We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving your problem-solving skills and preparing for technical interviews.

Additional Resources

For further reading and practice, consider the following resources: