# Tree - Diameter of a Binary Tree

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

PostOrder DFS

## 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:**

1
2
3

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:**

1
2

Input: root = [1,2]
Output: 1

## Solution

The

**diameter**can be calculated by using the**height**of`left`

and`right`

sub-tree. Hence in every traversal the height of the tree needed to be returned.- In order the math to work out, notice calculation of the base case scenario.
- The
`height`

of the`None`

node is set to`-1`

. - The calculation of
`diameter`

is`2+left_height+right_height`

. - The calculation of
`height`

is`1+max(left_height, right_height)`

.

- The
- Using
**post order traversal**the diameter at every node will be calculated from bottom-up, this way the TC will be`O(n)`

Below are two examples of how both `diameter`

and `height`

are calculated.

Let’s start with a `result`

array which will hold diameters from every node of the tree. Then we can find the max and return that.

1

diameters = []

We will be using **PostOrder** DFS (BFS can also be used). Starting with the base case, as we have already discussed, the height of `None`

node is `-1`

(this is mostly for the math to work for any tree).

1
2
3

def dfs(root):
if not root:
return -1

Now calculate the `left`

and `right`

height of the `root`

node. For a node with no leaf node, will have `left_height = -1`

and `right_height = -1`

returned from base condition (As shown in the diagram above).

1
2

left_height = dfs(root.left)
right_height = dfs(root.right)

Calculate the `diameter`

.

1

diameter = 2 + left_height + right_height

Append the `diameter`

to `diameters`

array.

1

diameters.append(diameter)

Now need to calculate the `height`

to be returned.

1
2

height = 1 + max( left_height, right_height)
return height

Finally invoke the `dfs()`

function and return `max`

from the `diameters`

array.

1
2

dfs(root)
return max(diameters)

## Final Code

Here is the full code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def diameter_of_binary_tree(root:TreeNode):
diameters = []
def dfs(root):
if not root:
return -1
left_height = dfs(root.left)
right_height = dfs(root.right)
diameter = 2 + left_height + right_height
diameters.append(diameter)
height = 1 + max(left_height,right_height)
return height
dfs(root)
return max(diameters)