Diameter Of Binary Tree Leetcode Problem 543 [Python Solution]

Problem Overview

In this article, we will tackle the Diameter Of Binary Tree problem.

This LeetCode problem is categorized under Trees and is considered easy in terms of difficulty.

The goal is to find the length of the diameter of a given binary tree.

The diameter 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.

Let's take a look at an example to better understand this problem:

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: The longest path is [4,2,1,3] or [5,2,1,3].

In the example above, we are given a binary tree, and the diameter is the length of the longest path, which can be observed from node 4 to node 3, passing through node 1. The length of this path is 3.

Constraints

Before we dive into the solution, let's consider the constraints of the problem:
– The number of nodes in the tree is in the range [1, 104].
– The values of the nodes are in the range [-100, 100].

Now that we understand the problem and its constraints, let's explore different approaches to solving it.

Understanding the Constraints

Before we delve into the solution, let's take a moment to understand what the constraints mean for this problem.

The number of nodes in the tree is between 1 and 104. This means that the tree can have a maximum of 104 nodes.

We need to ensure that our solution is efficient enough to handle large inputs without exceeding time or space limits.

The values of the nodes are between -100 and 100. This constraint doesn't directly affect the algorithm's complexity but reminds us that we are working with integers in this problem.

Problem Solution

To find the diameter of a binary tree, we can use a depth-first search (DFS) approach.

We will create a function that traverses the tree and computes both the height and the diameter of the tree.

By doing this, we can find the length of the longest path between any two nodes in the tree.

Python Code Solution

View on GitHub ➹

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: Optional[TreeNode]) -&gt; int:
        res = 0

        def dfs(root):
            nonlocal res

            if not root:
                return 0
            left = dfs(root.left)
            right = dfs(root.right)
            res = max(res, left + right)

            return 1 + max(left, right)

        dfs(root)
        return res

In the code above, we define a TreeNode class to represent the nodes of the binary tree.

We also create a Solution class with a method diameterOfBinaryTree that takes the root of the binary tree as input and returns the length of the diameter.

Here's how the solution works:
1. We initialize a variable res to store the result, which will be the diameter of the tree.

We define a nested function dfs that takes a node as an argument.

This function will perform a depth-first search on the binary tree.

Inside the dfs function, we handle the base case.

If the current node is None, we return 0 because the height of an empty subtree is 0.

We recursively call the dfs function on the left and right subtrees to find their heights.

We store the heights in the variables left and right.

We update the res variable by taking the maximum of its current value and the sum of left and right.

This step helps us keep track of the longest diameter found so far.

Finally, we return the height of the current subtree, which is 1 + max(left, right).

The +1 accounts for the edge connecting the current node to its child.

We call the dfs function with the root of the tree to start the DFS traversal.
After the traversal is complete, we return the final value of res, which represents the diameter of the binary tree.

Time and Space Complexity

Time Complexity

The time complexity of this solution is O(N), where N is the number of nodes in the binary tree.

We traverse each node once in a depth-first manner.

Space Complexity

The space complexity is O(N) as well.

This is because in the worst case, the recursion stack can have a depth of N, where N is the number of nodes in the tree.

Reasoning Behind Our Approach

The approach we used in our solution is based on a depth-first search (DFS) of the binary tree.

By recursively traversing the tree and calculating the height of each subtree, we can efficiently find the diameter of the tree.

The key insight in this approach is that we don't need to traverse the same subtree multiple times.

Instead, we compute the height and diameter of each subtree as we go up the tree, allowing us to find the longest path in a single pass.

Here's a breakdown of our approach:

We start the DFS traversal from the root of the tree and recursively explore its left and right subtrees.
For each node, we calculate the height of its left and right subtrees using the DFS approach.
As we calculate the heights, we also keep track of the longest diameter we've seen so far.

This is done by comparing the sum of the left and right subtree heights with the current maximum diameter.

The height of the current subtree is computed as 1 plus the maximum height between the left and right subtrees.

This is because the height of the subtree includes the edge connecting the current node to its child.

After the DFS traversal is complete, we return the maximum diameter we found during the process.

The use of a global res variable allows us to store and update the maximum diameter efficiently.

The recursive approach ensures that each subtree is explored only once, making this solution efficient and optimal.

Conclusion

In this article, we tackled the Diameter Of Binary Tree problem, a LeetCode question categorized under Trees and labeled as easy.

We provided a Python solution that uses a depth-first search (DFS) approach to find the diameter of a binary tree efficiently.

Understanding the problem, its constraints, and our approach is crucial for solving tree-related problems.

By applying DFS and recursion, we were able to find the longest path in the tree and calculate the diameter.

Remember that the time and space complexity of our solution is O(N), where N is the number of nodes in the tree.

This solution efficiently handles large inputs within the specified constraints.

If you found this article helpful, please like and engage to support the our platform.

If you have any questions, suggestions, or comments, feel free to share them below.

Happy coding!

LeetCode Problem Link

This blog post presented a detailed solution to the Diameter Of Binary Tree problem on LeetCode.

It explained the problem, provided a

Python solution, analyzed the time and space complexity, and offered reasoning behind the chosen approach.

By understanding the problem's constraints and applying a depth-first search (DFS) approach, we successfully solved this tree-related problem.

We hope this article has been helpful to you, and we encourage you to ask questions, provide suggestions, and share the content.