543. Diameter of Binary Tree
Problem Description
You're given the root of a binary tree and need to find 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 is measured by counting the number of edges between the nodes.
Key points to understand:
- The longest path might pass through the root node, but it doesn't have to
- The path length is counted as the number of edges (not nodes)
- You need to find the maximum possible path length between any two nodes in the entire tree
For example, if you have a tree where the longest path goes from a leaf in the left subtree, up through some parent nodes, and down to a leaf in the right subtree, that total edge count would be the diameter.
The solution works by using a depth-first search (DFS) approach. For each node, it:
- Calculates the maximum depth of the left subtree (
l
) - Calculates the maximum depth of the right subtree (
r
) - The potential diameter through this node is
l + r
(sum of left and right depths) - Updates the global maximum diameter if this path is longer
- Returns
1 + max(l, r)
to represent the depth from this node to its parent
The ans
variable keeps track of the maximum diameter found across all nodes, and this is returned as the final answer.
Flowchart Walkthrough
First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:
Is it a graph?
- Yes: A binary tree is a special type of graph where each node has at most two children and there are no cycles.
Is it a tree?
- Yes: The problem explicitly states we're working with a binary tree structure.
DFS
- We arrive at DFS: Since we're dealing with a tree structure, the flowchart leads us directly to using Depth-First Search.
Conclusion: The flowchart suggests using a DFS (Depth-First Search) approach for solving the diameter of binary tree problem.
This makes sense because:
- We need to explore the entire tree to find the longest path
- For each node, we need to calculate the depth of its left and right subtrees
- DFS naturally allows us to traverse to the leaf nodes first and then bubble up the depth information
- As we return from recursive calls, we can compute the diameter at each node by adding the left and right depths
- The recursive nature of DFS perfectly matches the recursive structure of the tree
Intuition
The key insight is that the longest path in a tree must have two endpoints, and these endpoints must be leaf nodes (or the root if it has only one child). Any longest path can be thought of as going "up" from one leaf to some common ancestor node, then "down" to another leaf.
For any node in the tree, if we consider it as the "peak" or "turning point" of a path, the longest path through that node would be:
- The deepest path in its left subtree + The deepest path in its right subtree
This is because we want to go as deep as possible on the left side, then turn at this node, and go as deep as possible on the right side.
So our strategy becomes:
- For each node, calculate how deep we can go in its left subtree
- Calculate how deep we can go in its right subtree
- The diameter through this node = left depth + right depth
- Keep track of the maximum diameter seen so far
But here's the clever part: while we're calculating potential diameters, we also need to return depth information to parent nodes. When returning to a parent, we can only take one path (either left or right), so we return 1 + max(left_depth, right_depth)
to indicate the maximum depth from that node.
This way, in a single DFS traversal, we accomplish two things:
- Calculate the diameter at each node (by summing left and right depths)
- Return the depth information needed by parent nodes to calculate their diameters
The beauty of this approach is that we only visit each node once, making it an efficient O(n) solution.
Learn more about Tree, Depth-First Search and Binary Tree patterns.
Solution Approach
We implement the solution using DFS (Depth-First Search) with a helper function that serves dual purposes: calculating depths and updating the diameter.
Implementation Details:
-
Main Function Setup:
- Initialize a variable
ans = 0
to track the maximum diameter found - Call the DFS helper function starting from the root
- Return the final answer
- Initialize a variable
-
DFS Helper Function: The
dfs
function takes a node and returns the maximum depth from that node to any leaf in its subtree.Base Case:
- If the node is
None
, return0
(no depth)
Recursive Case:
- Recursively calculate the maximum depth of the left subtree:
l = dfs(root.left)
- Recursively calculate the maximum depth of the right subtree:
r = dfs(root.right)
Update Global Maximum:
- The diameter through the current node is
l + r
(sum of depths from both sides) - Update the global answer:
ans = max(ans, l + r)
- We use
nonlocal ans
to modify the outer scope variable
Return Value:
- Return
1 + max(l, r)
to the parent - The
1
represents the edge from current node to its parent max(l, r)
gives the longer path to choose when going up to the parent
- If the node is
-
Why This Works:
- Each node is visited exactly once during the traversal
- At each node, we calculate the potential diameter if the longest path passes through it
- The global maximum tracks the best diameter found across all nodes
- The return value ensures parent nodes get correct depth information for their calculations
Time Complexity: O(n) where n is the number of nodes, as we visit each node once
Space Complexity: O(h) where h is the height of the tree, due to the recursion call stack
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let me walk through a concrete example to illustrate how this solution works.
Consider this binary tree:
1 / \ 2 3 / \ 4 5
Step-by-step execution:
-
Start at root (node 1):
- First, we need to get depths from left and right subtrees
- Call
dfs(node 2)
for left subtree
-
At node 2:
- Call
dfs(node 4)
for left child
- Call
-
At node 4 (leaf):
- Left child is None →
l = 0
- Right child is None →
r = 0
- Diameter through node 4:
l + r = 0 + 0 = 0
- Update
ans = max(0, 0) = 0
- Return to parent:
1 + max(0, 0) = 1
- Left child is None →
-
Back at node 2:
- Left depth from node 4:
l = 1
- Now call
dfs(node 5)
for right child
- Left depth from node 4:
-
At node 5 (leaf):
- Left child is None →
l = 0
- Right child is None →
r = 0
- Diameter through node 5:
l + r = 0
ans
remains 0- Return to parent:
1 + max(0, 0) = 1
- Left child is None →
-
Back at node 2 (completing):
- Left depth:
l = 1
(from node 4) - Right depth:
r = 1
(from node 5) - Diameter through node 2:
l + r = 1 + 1 = 2
- Update
ans = max(0, 2) = 2
- Return to parent:
1 + max(1, 1) = 2
- Left depth:
-
Back at root (node 1):
- Left depth from node 2:
l = 2
- Now call
dfs(node 3)
for right child
- Left depth from node 2:
-
At node 3 (leaf):
- Left child is None →
l = 0
- Right child is None →
r = 0
- Diameter through node 3:
l + r = 0
ans
remains 2- Return to parent:
1 + max(0, 0) = 1
- Left child is None →
-
Back at root (node 1, completing):
- Left depth:
l = 2
(from node 2) - Right depth:
r = 1
(from node 3) - Diameter through node 1:
l + r = 2 + 1 = 3
- Update
ans = max(2, 3) = 3
- Return:
1 + max(2, 1) = 3
(not used since this is root)
- Left depth:
Final answer: 3
The longest path is: node 4 → node 2 → node 1 → node 3, which has 3 edges.
Notice how:
- At each node, we calculate the potential diameter by summing left and right depths
- The maximum diameter (3) occurs at the root node in this case
- Each node returns its depth to help parent nodes calculate their diameters
- We only traverse each node once, making this efficient
Solution Implementation
1# Definition for a binary tree node.
2# class TreeNode:
3# def __init__(self, val=0, left=None, right=None):
4# self.val = val
5# self.left = left
6# self.right = right
7
8from typing import Optional
9
10class Solution:
11 def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
12 """
13 Calculate the diameter of a binary tree.
14 The diameter is the length of the longest path between any two nodes.
15 This path may or may not pass through the root.
16
17 Args:
18 root: The root node of the binary tree
19
20 Returns:
21 The diameter (number of edges) of the binary tree
22 """
23 # Initialize the maximum diameter found so far
24 self.max_diameter = 0
25
26 def calculate_height(node: Optional[TreeNode]) -> int:
27 """
28 Calculate the height of the tree rooted at the given node.
29 Also update the maximum diameter during traversal.
30
31 Args:
32 node: Current node being processed
33
34 Returns:
35 The height of the subtree rooted at this node
36 """
37 # Base case: empty node has height 0
38 if node is None:
39 return 0
40
41 # Recursively calculate heights of left and right subtrees
42 left_height = calculate_height(node.left)
43 right_height = calculate_height(node.right)
44
45 # The diameter passing through this node is the sum of
46 # left and right subtree heights
47 current_diameter = left_height + right_height
48
49 # Update the maximum diameter if current is larger
50 self.max_diameter = max(self.max_diameter, current_diameter)
51
52 # Return the height of this subtree (1 + max height of children)
53 return 1 + max(left_height, right_height)
54
55 # Start the DFS traversal from root
56 calculate_height(root)
57
58 # Return the maximum diameter found
59 return self.max_diameter
60
1/**
2 * Definition for a binary tree node.
3 * public class TreeNode {
4 * int val;
5 * TreeNode left;
6 * TreeNode right;
7 * TreeNode() {}
8 * TreeNode(int val) { this.val = val; }
9 * TreeNode(int val, TreeNode left, TreeNode right) {
10 * this.val = val;
11 * this.left = left;
12 * this.right = right;
13 * }
14 * }
15 */
16class Solution {
17 // Global variable to track the maximum diameter found
18 private int maxDiameter;
19
20 /**
21 * Calculates the diameter of a binary tree.
22 * The diameter is the length of the longest path between any two nodes,
23 * which may or may not pass through the root.
24 *
25 * @param root The root node of the binary tree
26 * @return The diameter of the binary tree
27 */
28 public int diameterOfBinaryTree(TreeNode root) {
29 maxDiameter = 0;
30 calculateHeight(root);
31 return maxDiameter;
32 }
33
34 /**
35 * Recursively calculates the height of the tree while updating the maximum diameter.
36 * For each node, the diameter passing through it equals left height + right height.
37 *
38 * @param node The current node being processed
39 * @return The height of the subtree rooted at the current node
40 */
41 private int calculateHeight(TreeNode node) {
42 // Base case: null node has height 0
43 if (node == null) {
44 return 0;
45 }
46
47 // Recursively calculate the height of left subtree
48 int leftHeight = calculateHeight(node.left);
49
50 // Recursively calculate the height of right subtree
51 int rightHeight = calculateHeight(node.right);
52
53 // Update the maximum diameter if the path through current node is longer
54 // The diameter through current node = left height + right height
55 maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
56
57 // Return the height of current subtree
58 // Height = 1 (current node) + maximum height of its subtrees
59 return 1 + Math.max(leftHeight, rightHeight);
60 }
61}
62
1/**
2 * Definition for a binary tree node.
3 * struct TreeNode {
4 * int val;
5 * TreeNode *left;
6 * TreeNode *right;
7 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
8 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
9 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
10 * };
11 */
12class Solution {
13public:
14 int diameterOfBinaryTree(TreeNode* root) {
15 int maxDiameter = 0;
16
17 // Lambda function to calculate the height of the tree while updating the diameter
18 // Returns the height of the subtree rooted at the given node
19 auto calculateHeight = [&](this auto&& calculateHeight, TreeNode* node) -> int {
20 // Base case: empty node has height 0
21 if (!node) {
22 return 0;
23 }
24
25 // Recursively calculate the height of left and right subtrees
26 int leftHeight = calculateHeight(node->left);
27 int rightHeight = calculateHeight(node->right);
28
29 // The diameter passing through this node is the sum of left and right heights
30 // Update the maximum diameter if current path is longer
31 maxDiameter = max(maxDiameter, leftHeight + rightHeight);
32
33 // Return the height of current subtree (1 + maximum of left or right height)
34 return 1 + max(leftHeight, rightHeight);
35 };
36
37 // Start the DFS traversal from root
38 calculateHeight(root);
39
40 // Return the maximum diameter found
41 return maxDiameter;
42 }
43};
44
1/**
2 * Definition for a binary tree node.
3 * class TreeNode {
4 * val: number
5 * left: TreeNode | null
6 * right: TreeNode | null
7 * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
8 * this.val = (val===undefined ? 0 : val)
9 * this.left = (left===undefined ? null : left)
10 * this.right = (right===undefined ? null : right)
11 * }
12 * }
13 */
14
15/**
16 * Calculates the diameter of a binary tree.
17 * The diameter is the length of the longest path between any two nodes in the tree.
18 * This path may or may not pass through the root.
19 *
20 * @param root - The root node of the binary tree
21 * @returns The diameter of the binary tree
22 */
23function diameterOfBinaryTree(root: TreeNode | null): number {
24 // Variable to track the maximum diameter found
25 let maxDiameter: number = 0;
26
27 /**
28 * Depth-first search helper function to calculate the height of each subtree
29 * while updating the maximum diameter.
30 *
31 * @param node - The current node being processed
32 * @returns The height of the subtree rooted at the current node
33 */
34 const calculateHeight = (node: TreeNode | null): number => {
35 // Base case: if node is null, height is 0
36 if (!node) {
37 return 0;
38 }
39
40 // Recursively calculate the height of left and right subtrees
41 const leftHeight: number = calculateHeight(node.left);
42 const rightHeight: number = calculateHeight(node.right);
43
44 // Update the maximum diameter if the path through current node is longer
45 // The diameter through current node = left height + right height
46 maxDiameter = Math.max(maxDiameter, leftHeight + rightHeight);
47
48 // Return the height of current subtree (1 + maximum height of children)
49 return 1 + Math.max(leftHeight, rightHeight);
50 };
51
52 // Start the DFS traversal from the root
53 calculateHeight(root);
54
55 // Return the maximum diameter found
56 return maxDiameter;
57}
58
Time and Space Complexity
Time Complexity: O(n)
The algorithm performs a depth-first search (DFS) traversal of the binary tree. Each node is visited exactly once during the traversal. At each node, the algorithm performs constant time operations: calculating the maximum value, updating the answer variable, and returning the height. Since we visit all n
nodes exactly once and perform O(1)
work at each node, the total time complexity is O(n)
.
Space Complexity: O(n)
The space complexity is determined by the recursive call stack used during the DFS traversal. In the worst case, the binary tree is completely unbalanced (essentially a linked list), where all nodes are arranged in a single path. This would result in a recursion depth of n
, requiring O(n)
space on the call stack. In the best case of a perfectly balanced tree, the recursion depth would be O(log n)
, but we consider the worst-case scenario for space complexity analysis, which is O(n)
.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Confusing Node Count vs Edge Count
One of the most frequent mistakes is counting nodes instead of edges when calculating the diameter. The problem specifically asks for the number of edges in the longest path, not the number of nodes.
Incorrect Approach:
def diameterOfBinaryTree(self, root):
self.max_diameter = 0
def dfs(node):
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
# WRONG: Adding 1 for the current node when updating diameter
self.max_diameter = max(self.max_diameter, left + right + 1)
return 1 + max(left, right)
dfs(root)
return self.max_diameter
Why it's wrong: Adding 1 when calculating the diameter counts the current node, making it a node count rather than an edge count.
Correct Approach:
# The diameter through current node is simply left + right (edges only)
self.max_diameter = max(self.max_diameter, left + right)
2. Using Local Variable Instead of Instance/Nonlocal Variable
Attempting to use a local variable to track the maximum diameter won't work because integers are immutable in Python, and the variable won't be accessible across recursive calls.
Incorrect Approach:
def diameterOfBinaryTree(self, root):
max_diameter = 0 # Local variable
def dfs(node):
if not node:
return 0
left = dfs(node.left)
right = dfs(node.right)
# This won't work - can't modify local variable from outer scope
max_diameter = max(max_diameter, left + right) # UnboundLocalError
return 1 + max(left, right)
dfs(root)
return max_diameter
Solutions:
Option 1 - Use instance variable (shown in solution):
self.max_diameter = 0 # Instance variable accessible throughout
Option 2 - Use nonlocal keyword:
def diameterOfBinaryTree(self, root):
max_diameter = 0
def dfs(node):
nonlocal max_diameter # Declare nonlocal to modify outer variable
# ... rest of the code
Option 3 - Use a mutable container:
def diameterOfBinaryTree(self, root):
max_diameter = [0] # List is mutable
def dfs(node):
# ... calculate left and right
max_diameter[0] = max(max_diameter[0], left + right)
# ...
dfs(root)
return max_diameter[0]
3. Forgetting to Handle Single Node or Empty Tree
While the provided solution handles these cases correctly through the base case, beginners might write solutions that don't properly handle edge cases.
Potential Issue:
- Empty tree (root = None): Should return 0
- Single node tree: Should return 0 (no edges)
- Tree with only two nodes: Should return 1 (one edge)
Verification: Always test your solution with these minimal cases to ensure the base case and return values are correct.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Everything About Trees A tree is a type of graph data structure composed of nodes and edges Its main properties are It is acyclic doesn't contain any cycles There exists a path from the root to any node Has N 1 edges where N is the number of nodes in the tree and
https assets algo monster cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS As the name suggests
Binary Tree Min Depth Prereq BFS on Tree problems bfs_intro Given a binary tree find the depth of the shallowest leaf node https assets algo monster binary_tree_min_depth png Explanation We can solve this problem with either DFS or BFS With DFS we traverse the whole tree looking for leaf nodes and record and update the minimum depth as we go With BFS though since we search level by level we are guaranteed to find the shallowest leaf node
Want a Structured Path to Master System Design Too? Don’t Miss This!