543 Diameter of Binary Tree

1. Description

Given the root of a binary tree, return the length of a 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.

 

constraints :

• The number of nodes in the tree is in the range [1, \(10^{4}\)].
• -100 <= Node.val <= 100

 

2. Algorithms

The diameter of current node can get by adding max depth of left subtree and right subtree. After we get the diameter, we can compare previous max diameter with current max diameter.

 

The workflow of calculating max depth of current node follows below order :

1. Return 0, if the val of current node is None. (base case)
2. Return max depth of left subtree and right subtree, incrementing it by 1.

While we caculate the max depth of current node, we can update max diameter by adding two values : maxDepth(root.left) and maxDepth(root.right).

 

1. Start
2. Declare variable named maxDiameter initialized to 0.
3. Declare function named helper which got root as input.
   
   1. (Base case) If root is None, return 0.
   2. Calculate left depth and right depth of current node recursively. Store them into variable named left and right.
   3. Update value of maxDiamter with the max value between previous maxDiameter and current Diameter(left + right).
   4. Return result of 1 + max(left, right)
4. Operate helper function.
5. Return the calculated maxDiameter.
6. End

 

3. Codes

# 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:
    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        maxDiameter = 0 
        def helper(root) : 
            nonlocal maxDiameter 
            
            if root is None : 
                return 0
            
            left = helper(root.left)
            right = helper(root.right) 
            
            maxDiameter = max(maxDiameter, left + right)
            
            return 1 + max(left, right) 
        helper(root)
        return maxDiameter

 

4. Conclusion