Diameter of a Binary Tree - Leetcode 543 - Python

0:00 - Read the problem
1:35 - Drawing Explanation
12:45 - Coding Solution

leetcode 543

#tree #diameter #python

[NeetCode]

It's half the length and still covers everything.

[Obligedcartoon]

Alternative mathematical approach: It made a little more sense to me to return 0 for a Null node. In doing so, you don't need the + 2 in the updating of the result. You are essentially accounting for the parent edge in different ways. I found this approach to come a little more naturally to me, so I'm posting in case it helps anyone!

def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:

def dfs(root):
nonlocal diameter
if root is None:
return 0
left = dfs(root.left)
right = dfs(root.right)

diameter = max(left + right, diameter)

return max(left, right) + 1


diameter = 0
dfs(root)
return diameter

[chiranjeevipippalla]

If you are new to Data Structures and don’t understand recursion concept in Trees, don’t worry. I used to be like that until I find this channel sometime ago. White boarding is a must practice to understand Trees. Watch as many videos as possible. Later you can worry about the code. It will be that one snap of a moment you need to wait for to realize that you understood Trees. I had that snap of a moment. Don’t give up. We are Engineers 👩‍💻 👨‍💻

[TheElementFive]

In what universe is this an "easy" problem?

[Deescacha]

I think this problem deserves an update. The way you explained it is pretty complicated. It's way more intuitive to simply count the number of edges.

```
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
if not root: return 0

diameter = 0

def dfs(node):
if not node: return 0
edges_l = dfs(node.left) if node.left else 0
edges_r = dfs(node.right) if node.right else 0
nonlocal diameter
diameter = max(diameter, edges_l + edges_r)
edges = 1 + max(edges_l, edges_r)
return edges

dfs(root)

return diameter
```

[alisbai]

This one is quite difficult, do you think it should be labeled as medium?

[shaanwalia]

I found this explanation quite difficult to follow, especially around 8:19, when NeetCode starts talking about "convention" to make the math work. The solution works, yes, but I am left a little dissatisfied with the overall explanation as it is still quite unclear. I don't seem to find this convention being used in other problems, but maybe that's because I haven't done enough of them yet.

[ax]

thank you. The tricky part of this problem is the -1, +1, height, diameter. So many tutorials just take them for granted and offer no explanation, but you did an amazing job talking about the whys. Bags of thanks!

[alexeyabramov]

First of all, thanks for this fantastic channel! However, for this problem I find the following code way easier:

def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:

def traversal(root):
nonlocal max_d
if not root:
return 0

left_d = traversal(root.left)
right_d = traversal(root.right)
max_d = max(left_d + right_d, max_d)
return max(left_d, right_d) + 1

max_d = 0
traversal(root)

return max_d

[CodenameAvatar]

The arithmetic is unnecessary: if we return 0 in basecase and set diameter = left+right, the solution is still the same.

[samer]

I felt I could easily get so confused by this tricky -1 counting algo... later I found out another alternative which seems more clear to me is to just use max() to include both cases instead:

def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
ans = 0
def longestPath(node):
if not node: return 0

left = longestPath(node.left)
right = longestPath(node.right)

nonlocal ans
ans = max(ans, left + right)
return max(left, right) + 1

longestPath(root)
return ans

[YashGupta-tyhn]

I think this solution will be a bit simpler to understand

class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
def dfs(root):
nonlocal res
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
res = max(res, left + right + 1)
return 1 + max(left, right)
res = 0
dfs(root)
return res - 1

[Tyokok]

Great video! One question, why you use list type global res? why cannot you just use res=0 ? Thank you!

[lucaswang]

Out of so many videos, this is the first time that I think my solution is more clear and self-explained. :).

// Notice that when the tree is like a triangle, its maxDiamter is just left tree height plus right tree height.
var diameterOfBinaryTree = function (root) {
/**
* Returns the height of a tree.
* A tree with a single node is of height 1.
*/
function getHeight(cur) {
if (!cur) return 0; // The end of tree, height is 0

const leftHeight = getHeight(cur.left);
const rightHeight = getHeight(cur.right);

const curDiameter = leftHeight + rightHeight;
maxDiameter = Math.max(maxDiameter, curDiameter);

return 1 + Math.max(leftHeight, rightHeight);
}

let maxDiameter = 0;
getHeight(root);
return maxDiameter;
};

[ancai]

The core idea for this issue is pretty much the same as the Hard problem max path sum(lc 124),
for a node, we have two options,
1. split
2. no split

if we split at the current node, we'll have to calculate the path left -> current-> right.
In contrast, if we don't split we'll have to return the max path the current node could return to its parent.

Hope it helps

[therealjulian]

Don't feel bad if you can't understand this solution, it's messy and unintuitive. There are much better solutions out there!

[mathematicalninja]

I cracked at 'The leftsubtree is left right'

[sayantankundu]

This explanation and code is wayyyy better than the one on GFG... Thanks a lot!! ❤

[shreeshanmukh]

I made use of the maximumDepth problem to get the depths of the subtrees of a node, added them to get the diameter wrt a node. Then recursively called the diameter function on the left and right children and returned the max of the three. I felt this made sense to me from understanding standpoint. Putting my code for reference.

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
#find the depth of left and right subtree from each node. Sum them to get the diameter wrt that node.
#recursively call the same fn on the right and left child to get the same.
#return the maximum of the three i.e., current diameter, diameter of right child, diameter of left child.

def depth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0

right = 1 + self.depth(root.right)
left = 1 + self.depth(root.left)

return max(right, left)

def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
if not root:
return 0

rightdepth = self.depth(root.right) if root.right else 0
leftdepth = self.depth(root.left) if root.left else 0

dia = rightdepth + leftdepth

return max(dia, self.diameterOfBinaryTree(root.right), )


Hope this helps!

[zhouwang]

Creating a list to store the update result is so inspiring.