---
tags: data_structure_python
---

# Diameter of Binary Tree <img src="https://img.shields.io/badge/-easy-brightgreen">

Given a binary tree, you need to compute 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.

<ins>**Example:**</ins>

Given a binary tree

          1
         / \
        2   3
       / \     
      4   5    

Return 3, which is the length of the path ```[4,2,1,3]``` or ```[5,2,1,3]```.

**Note:** The length of path between two nodes is represented by the number of edges between them.

# Solution

### Solution 1: First approach DFS

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        # Time complexity: O(n^2)
        if root is None:
            return 0
        else:
            return max(self.dfs(root.left) + self.dfs(root.right),
                       self.diameterOfBinaryTree(root.left), 
                       self.diameterOfBinaryTree(root.right))
                       
    def dfs(self, root):
        if root is None:
            return 0
        else:
            return 1 + max(self.dfs(root.left), self.dfs(root.right))

### Solution 2: Second approach DFS

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        if root == None:
            return 0
        else:
            longest_path = -1
            _, longest_path = self.dfs(root, longest_path)
            return longest_path
            
    def dfs(self, root, longest_path):
        if root == None:
            return 0, longest_path
        else:
            left, longest_path = self.dfs(root.left, longest_path)
            right, longest_path = self.dfs(root.right, longest_path)
            
            if left + right > longest_path:
                longest_path = left + right
                
            return 1 + max(left, right), longest_path