Calculate the Diameter of a Binary Tree

54.5k
0

Given the root of a binary tree, return the diameter of the tree.

The diameter is the length of the longest path between any two nodes. This path may or may not pass through the root.

The path length is measured using the number of edges, not nodes. Therefore, a tree containing only one node has diameter 0.

Example 1

Input: root = [1, 2, 3, 4, 5]

Output: 3

Explanation: The longest path can be 4 -> 2 -> 1 -> 3 or 5 -> 2 -> 1 -> 3. Both paths contain 3 edges, so the diameter is 3.

Example 2

Input: root = [1, 2]

Output: 1

Explanation: The longest path is from node 2 to node 1. This path contains exactly one edge.

Example 3

Input: root = [1]

Output: 0

Explanation: There is only one node, so there is no edge between two different nodes. Therefore, the diameter is 0.

Brute Force Approach

For any node, the longest path passing through it can extend to the deepest node in its left subtree and the deepest node in its right subtree.

If the heights of the child subtrees are measured in nodes, then:

leftHeight + rightHeight

directly gives the number of edges in the path passing through the current node.

However, the actual diameter may lie completely inside the left or right subtree. Therefore, every node must be considered as a possible highest point of the longest path.

The drawback is that subtree heights are recalculated for different ancestors, which creates repeated work.

Algorithm

  • If the current node is null, return 0 because an empty subtree has no diameter.

  • Use a helper findHeight to calculate the height of a subtree in terms of nodes.

  • Calculate leftHeight and rightHeight from the current node's children.

  • Use leftHeight + rightHeight as the diameter passing through the current node.

  • Recursively find the best diameter in the left and right subtrees because the longest path may not pass through the current node.

  • Return the maximum among the current path, left-subtree diameter, and right-subtree diameter.

Dry Run

Diameter of Binary Tree Brute Froce Dry Run.png

Diameter of Binary Tree Brute Froce Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
private:
// Returns subtree height
// measured in nodes.
int findHeight(TreeNode* node) {
// An empty subtree
// has height zero.
if (node == nullptr) {
return 0;
}
int leftHeight = findHeight(node->left);
int rightHeight = findHeight(node->right);
return 1 + max(leftHeight, rightHeight);
}
// Checks every node as the
// highest point of the diameter.
int findDiameter(TreeNode* node) {
// An empty subtree
// has diameter zero.
if (node == nullptr) {
return 0;
}
// Heights from both children form
// the path through this node.
int leftHeight = findHeight(node->left);
int rightHeight = findHeight(node->right);
int currentDiameter =
leftHeight + rightHeight;
// The longest path may lie
// completely inside either subtree.
int leftDiameter =
findDiameter(node->left);
int rightDiameter =
findDiameter(node->right);
return max(
currentDiameter,
max(leftDiameter, rightDiameter)
);
}
public:
// Returns the diameter
// measured in edges.
int diameterOfBinaryTree(TreeNode* root) {
return findDiameter(root);
}
};
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
Solution solution;
cout << solution.diameterOfBinaryTree(root)
<< endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N × H), because subtree heights may be recomputed for different nodes. This becomes O(N²) for a skewed tree and O(N log N) for a balanced tree.

Space Complexity: O(H), where H is the tree height, due to the recursion stack.

Better Approach

A binary tree can be viewed as an undirected tree by treating every parent-child connection as a two-way edge.

For an unweighted tree, starting from any node and finding a farthest node gives one endpoint of a diameter. Running BFS again from that endpoint gives the maximum distance to the opposite endpoint, which is the diameter.

This approach runs in O(N) time, so it already removes the repeated work of the Brute Force Approach. However, converting the binary tree into an explicit graph requires O(N) additional space. The Optimal Approach keeps the same O(N) time complexity while avoiding this graph construction.

Algorithm

  • If root is null, return 0 because an empty tree has no diameter.

  • Convert every parent-child connection into two graph edges so that traversal can move in both directions.

  • Run BFS from root to find a node farthest from it. In a tree, this node can serve as one endpoint of a diameter.

  • Run a second BFS from this endpoint to find the farthest reachable node.

  • The maximum distance found during the second BFS is the diameter measured in edges.

  • Return this distance.

Dry Run

Diameter of Binary Tree Better Appraoch Dry Run.png

Diameter of Binary Tree Better Appraoch Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
private:
// Converts parent-child links
// into two-way graph edges.
void buildGraph(
TreeNode* node,
unordered_map<TreeNode*, vector<TreeNode*>>& graph
) {
// A null node adds no edge.
if (node == nullptr) {
return;
}
// Connect the left child
// in both directions.
if (node->left != nullptr) {
graph[node].push_back(node->left);
graph[node->left].push_back(node);
buildGraph(node->left, graph);
}
// Connect the right child
// in both directions.
if (node->right != nullptr) {
graph[node].push_back(node->right);
graph[node->right].push_back(node);
buildGraph(node->right, graph);
}
}
// Returns the farthest node
// and its distance from start.
pair<TreeNode*, int> bfs(
TreeNode* start,
unordered_map<TreeNode*, vector<TreeNode*>>& graph
) {
queue<pair<TreeNode*, int>> q;
unordered_set<TreeNode*> visited;
q.push({start, 0});
visited.insert(start);
TreeNode* farthestNode = start;
int maxDistance = 0;
// BFS explores nodes by
// increasing edge distance.
while (!q.empty()) {
auto [node, distance] = q.front();
q.pop();
// Track the farthest node
// reached so far.
if (distance > maxDistance) {
maxDistance = distance;
farthestNode = node;
}
// Visit each neighbor once
// to avoid moving in cycles.
for (TreeNode* neighbor : graph[node]) {
if (!visited.count(neighbor)) {
visited.insert(neighbor);
q.push({
neighbor,
distance + 1
});
}
}
}
return {farthestNode, maxDistance};
}
public:
// Finds the diameter using
// two BFS traversals.
int diameterOfBinaryTree(TreeNode* root) {
// An empty tree
// has diameter zero.
if (root == nullptr) {
return 0;
}
unordered_map<TreeNode*, vector<TreeNode*>>
graph;
buildGraph(root, graph);
// First BFS finds one
// endpoint of a diameter.
TreeNode* endpoint =
bfs(root, graph).first;
// Second BFS finds the
// diameter from that endpoint.
int diameter =
bfs(endpoint, graph).second;
return diameter;
}
};

Complexity Analysis

Time Complexity: O(N), because building the graph takes O(N) time and each of the two BFS traversals visits every node and edge at most once.

Space Complexity: O(N), because the adjacency list explicitly stores the tree as a graph, while the visited structure and BFS queue may also contain up to N nodes.

Optimal Approach

The Brute Force Approach already gives the required relation:

diameter through a node = leftHeight + rightHeight

Its inefficiency comes from recalculating subtree heights for different nodes. Post-order DFS removes this repeated work by calculating each subtree height exactly once.

At every node, the left and right subtree heights are first obtained. Their sum gives the diameter passing through that node, while only the larger of the two heights can continue upward to the parent.

Like the BFS approach, this solution runs in O(N) time. Its main advantage is that it works directly on the binary tree and avoids constructing an explicit graph. Therefore, its auxiliary space is only the recursion stack, O(H), instead of the O(N) graph storage required by BFS.

Algorithm

  • Initialize diameter = 0 to store the longest path found so far.

  • Use a recursive helper that returns the height of the current subtree in terms of nodes.

  • If the current node is null, return 0 because an empty subtree contributes no height.

  • Recursively calculate leftHeight and rightHeight before processing the current node.

  • Update diameter with leftHeight + rightHeight, since this is the number of edges in the longest path passing through the current node.

  • Return 1 + max(leftHeight, rightHeight) because only one downward branch can be extended by the parent.

Dry Run

Diameter of Binary Tree Optimal Appraoch Dry Run.png

Diameter of Binary Tree Optimal Appraoch Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int value) {
val = value;
left = nullptr;
right = nullptr;
}
};
class Solution {
private:
// Returns subtree height
// while updating the diameter.
int findHeight(
TreeNode* node,
int& diameter
) {
// An empty subtree
// contributes height zero.
if (node == nullptr) {
return 0;
}
int leftHeight =
findHeight(node->left, diameter);
int rightHeight =
findHeight(node->right, diameter);
// Both branches can form
// a path through this node.
diameter = max(
diameter,
leftHeight + rightHeight
);
// Only one branch can
// continue toward the parent.
return 1 + max(
leftHeight,
rightHeight
);
}
public:
// Returns the diameter
// measured in edges.
int diameterOfBinaryTree(TreeNode* root) {
int diameter = 0;
findHeight(root, diameter);
return diameter;
}
};
int main() {
TreeNode* root = new TreeNode(1);
root->left = new TreeNode(2);
root->right = new TreeNode(3);
root->left->left = new TreeNode(4);
root->left->right = new TreeNode(5);
Solution solution;
cout << solution.diameterOfBinaryTree(root)
<< endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N), because every node is processed exactly once. This is the same asymptotic time complexity as the BFS approach.

Space Complexity: O(H), where H is the height of the tree, because only the recursion stack is required. This becomes O(N) for a skewed tree and O(log N) for a balanced tree. Unlike the BFS approach, no explicit O(N) graph is constructed.

FAQs

Q1. Why is the diameter not calculated only at the root?

The longest path may lie completely inside the left or right subtree. Therefore, every node must be considered as a possible highest point of the diameter.

Q2. Why does leftHeight + rightHeight give the diameter through a node?

The height returned from each child counts nodes downward from that child. Those counts are exactly the number of edges from the current node into each side. Adding them gives the complete edge count of the path through the current node.

Q3. Why does the Optimal Approach return height instead of diameter?

The parent needs only the longest single downward branch it can extend. A diameter may use both branches at a node, so it is tracked separately.

Q4. What is a common mistake in this problem?

Counting nodes instead of edges. For example:

4 → 2 → 1 → 3

contains 4 nodes but only 3 edges, so the diameter is 3.

Q5. Can BFS be used to find the diameter?

Yes. After converting the binary tree into an undirected tree, two BFS traversals can find the diameter in O(N) time. Post-order DFS is generally simpler when the input is already given as a binary-tree root.

Binary Tree

Read Similar Blogs

Binary Tree

Parent and Distance - Introduction

Parent and Distance in a Binary Tree A binary tree normally stores connections from a node to its children: Left child Right child These connections make downward traversal straightforward. However...

117.9k
Binary Tree

Check If a Binary Tree Is a Subtree of Another Tree

Given the roots of two binary trees, root and subRoot , determine whether subRoot appears as a subtree of root . A subtree must match an entire tree section starting from some node in root , includ...

67.9k
Binary Tree

Count Nodes in a Complete Binary Tree

tuf-code-editor-4 cpp #include using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int value) { val = value; left = nullptr; right = nullptr; } }; class Soluti...

54.2k
Comments0