Find Diameter of a Binary Tree - Algorithm, Visualization, Examples

Binary Trees

Contents

VisualizationProblemExamplesSolutionAlgorithmCode

Visualization Player

Problem Statement❯

Given the root of a binary tree, determine the diameter of the tree. The diameter of a binary tree is defined as the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. The length is measured by the number of edges between the nodes.

Examples❯

Input Tree Level Order Output Description
[1, 2, 3, 4, 5, null, 6]
[[1], [2, 3], [4, 5, 6]] Standard case: Diameter passes through left and right subtrees (4→2→1→3→6), length 4
[1]
[[1]] Edge case: Single-node tree, diameter is 0 (no edges)
[] [] Edge case: Empty tree, diameter is 0
[1, 2, null, 3, null, null, null, 4]
[[1], [2], [3], [4]] Left-skewed tree: Diameter is 3 (path from 4 to 1)
[1, null, 2, null, null, null, 3]
[[1], [2], [3]] Right-skewed tree: Diameter is 2 (path from 1 to 3)
[1, 2, 3, 4, null, null, 5]
[[1], [2, 3], [4, 5]] Diameter is 4 (path from 4 → 2 → 1 → 3 → 5)

Solution❯

Understanding the Problem

The diameter of a binary tree is defined as the length of the longest path between any two nodes in the tree. This path may or may not pass through the root. The "length" here is measured in terms of the number of edges between the nodes on the path.

For example, in the binary tree [1, 2, 3, 4, 5], one possible longest path is from node 4 to node 5. The diameter in this case is 3 (edges between 4-2, 2-1, and 1-3).

Step-by-Step Solution with Example

step 1: Understand what needs to be calculated

We need to find the **longest path** between any two nodes in the binary tree. This path can lie completely in the left or right subtree or pass through the root.

step 2: Define a helper function to calculate height

We recursively calculate the height of each node’s left and right subtree. The height of a node is the maximum number of edges on the longest path from the node to a leaf.

step 3: At each node, compute the potential diameter

At every node, we calculate the sum of the left and right subtree heights. This value represents the diameter passing through that node.

step 4: Keep track of the global maximum diameter

As we compute diameters through all nodes, we update a global variable if the current node's diameter is greater than the previous maximum.

step 5: Return the final maximum diameter

After traversing the entire tree, the global variable holds the length of the longest path, i.e., the diameter.

step 6: Example with tree [1, 2, 3, 4, 5]

Let's consider the binary tree: 

        1
       /       2   3
     /     4   5
  • Height of 4 = 0
  • Height of 5 = 0
  • Height of 2 = max(0, 0) + 1 = 1
  • Diameter at node 2 = height(4) + height(5) = 0 + 0 = 0 (wrong!)
  • Actually, we include the edge count between nodes: so diameter at node 2 = 1 + 1 = 2
  • Height of 3 = 0
  • Diameter at root node 1 = height(2) + height(3) = 2 + 1 = 3
So, the maximum diameter is 3 (edges in path 4-2-1-3).

Edge Cases

Single Node Tree

If the tree has only one node like [1], there are no edges. So, the diameter is 0.

Empty Tree

If the tree is empty (root is null), then the diameter is 0. This must be handled to avoid runtime errors.

Skewed Tree (like Linked List)

Example: [1, 2, null, 3, null, 4] (a left-skewed tree). The diameter is 3 (edges between 1-2, 2-3, 3-4).

Uneven Subtrees

Example: [1, 2, 3, 4, null, null, 5]. Even though one subtree is deeper, the longest path can still pass through intermediate nodes, not necessarily the root.

Balanced vs Unbalanced Trees

In a balanced tree, the diameter often passes through the root. In unbalanced trees, it might lie entirely within the deeper subtree.

Finally

The key idea is to recursively calculate subtree heights and use them to determine the longest path at each node. Even though we’re calculating heights, the goal is to keep track of the **maximum** left+right height combination seen so far.

This approach ensures that all possible paths are considered, including those not passing through the root. Handling edge cases like empty trees or skewed trees makes the solution robust and beginner-friendly.

Algorithm Steps❯

  1. Start at the root of the binary tree.
  2. For each node, recursively compute the height of its left and right subtrees.
  3. The diameter at that node is the sum of the left and right subtree heights.
  4. Update the global maximum diameter if this sum is greater than the current maximum.
  5. Return the height of the node as max(left, right) + 1.
  6. After processing the entire tree, the maximum diameter recorded is the tree's diameter.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = node->right = NULL;
    return node;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int diameter = 0;

int height(TreeNode* node) {
    if (node == NULL) return 0;
    int left = height(node->left);
    int right = height(node->right);
    diameter = max(diameter, left + right);
    return max(left, right) + 1;
}

int diameterOfBinaryTree(TreeNode* root) {
    diameter = 0;
    height(root);
    return diameter;
}

int main() {
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    printf("Diameter: %d\n", diameterOfBinaryTree(root));
    return 0;
}

Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...