Leetcode – Diameter of Binary Tree Solution in Python

Introduction

Binary trees are one of the most fundamental data structures in computer science, finding extensive applications in various fields. Problems related to binary trees often require a solid understanding of tree traversal techniques. One such intriguing problem is the Diameter of Binary Tree, available on Leetcode. In this exhaustive article, we will explore the Diameter of Binary Tree problem, understand the essential concepts behind it, and develop a Python solution.

The Diameter of Binary Tree problem is described as follows:

Given the root of a binary tree, you need to compute 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.

For example:

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

Tree Depth and Diameter

Before diving into the solution, let’s establish an understanding of the relationship between the diameter of a binary tree and the depth of its subtrees. The diameter of a binary tree can be seen as the sum of the depths of the left and right subtrees of any node in the tree. In this problem, we are required to find the node for which the sum of the depths of its left and right subtrees is maximal.

Recursive Approach: Depth-First Search (DFS)

To solve this problem efficiently, we can perform a Depth-First Search (DFS) traversal of the binary tree. For each node, we recursively compute the depth of its left and right subtrees. While doing so, we can keep track of the maximum sum of depths we have seen so far, which corresponds to the diameter of the tree.

Here is the Python code for this approach.

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:
        # Function to compute the depth of a tree rooted at node
        def depth(node):
            nonlocal diameter
            if not node:
                return 0
            # Compute the depth of the left and right subtrees
            left_depth = depth(node.left)
            right_depth = depth(node.right)
            # Update the diameter
            diameter = max(diameter, left_depth + right_depth)
            # Return the depth of the tree rooted at node
            return max(left_depth, right_depth) + 1
        
        # Variable to store the diameter
        diameter = 0
        
        # Invoke the recursive function on the root
        depth(root)
        
        return diameter

This recursive approach has a time complexity of O(n), where n is the number of nodes in the tree, as we visit each node once. The space complexity is O(h), where h is the height of the tree, due to the recursive call stack.

Testing the Solution

Let’s test the solution with an example:

# Create a binary tree with root 1, and nodes 2, 3, 4, 5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)

# Initialize the solution class
solution = Solution()

# Get the diameter of the binary tree
print(solution.diameterOfBinaryTree(root))  # Output should be 3

Conclusion

In this detailed article, we explored the Diameter of Binary Tree problem on Leetcode. We understood the significance of tree depth in calculating the diameter and employed a recursive Depth-First Search approach to solve the problem efficiently.