# 543. Diameter of Binary Tree — LeetCode(Python)

--

I got you!

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

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

We can use a depth-first search (DFS) traversal algorithm to solve this problem.

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 —

Since we are visiting each node only a constant number of times, we can say that our algorithm requires a linear amount of time to run.

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)