Diameter of Binary Tree

Try to solve the Diameter of Binary Tree problem.

We'll cover the following

Statement#

Given a binary tree, you need to compute the length of the tree’s diameter. 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.

Note: The length of the 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,500][1, 500].
  • −100≤-100 \leq Node.value ≤100\leq 100

Examples#

Created with Fabric.js 3.6.6 4 Input: Binary tree 1 2 3 4 5 6 1 2 3 4 5 6 Sample example 1 The number of edges between red node 2 and red node6 is 4, which is the diameter of the tree.

1 of 3

Created with Fabric.js 3.6.6 Input: Binary tree 3 9 20 15 7 3 9 20 15 7 3 Sample example 2 The number of edges between red node 9 and red node15 is 3, which is the diameter of the tree.

2 of 3

Created with Fabric.js 3.6.6 2 Input: Binary tree 3 20 7 3 20 7 Sample example 3 The number of edges between red node 3 and red node7 is 2, which is the diameter of the tree.

3 of 3

Understand the problem#

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

Diameter of Binary Tree

1

What is the diameter of the following binary tree?

  5 / \6   7   / \  8   9
A)

2

B)

3

C)

4

D)

5

Question 1 of 40 attempted

Figure it out!#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct sequence.

Start traversing the tree from the root node.

For each node, calculate the height of the left and right subtree.

For each node, update the diameter using the following formula: max(diameter, left height + right height).

After traversing the whole tree, return the diameter value since it is the length of the tree’s diameter.

Try it yourself#

Implement your solution in main.py in the following coding playground.

Python
usercode > main.py
Input #1
%0 node_1 1 node_2 2 node_1->node_2 node_3 3 node_1->node_3 node_4 4 node_2->node_4 node_5 5 node_2->node_5 node_6 6 node_3->node_6
Visualization for Input #1
Diameter of Binary Tree

Tree Depth-first Search: Introduction

Solution: Diameter of Binary Tree