543. Diameter of Binary Tree — LeetCode(Python)

I got you!

Problem:

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, 104].
• -100 <= Node.val <= 100

Solution:

Explanation —

We can use a depth-first search (DFS) traversal algorithm to solve this problem.

The basic idea is that the diameter across a node is the sum of the maximum depths of it’s left subtree and right subtree.

So, at every node, we compute the height of the left subtree and that of the right subtree, which is what we return in max(l, r).

We, then, calculate the diameter dia across this node.

A max_dia variable is used to keep track of the largest such diameter across all nodes.

Finally, we return max_dia.

Time Complexity —

Since we are visiting each node only a constant number of times, we can say that our algorithm requires a linear amount of time to run.

Also, the recursion stack could be storing all nodes in the tree in case of a really skewed tree (like a linked list). So, we assume the space complexity to be linear in the worst case.

Thus, if n is the number of nodes in the given binary tree,

Time Complexity: O(n)

Space Complexity: O(n)

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏