543. Diameter of Binary Tree — LeetCode(Python)

I got you!

Problem:

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 —

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 —

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:

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store