Facebook Pixel

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:

  1. Calculates the maximum depth of the left subtree (l)
  2. Calculates the maximum depth of the right subtree (r)
  3. The potential diameter through this node is l + r (sum of left and right depths)
  4. Updates the global maximum diameter if this path is longer
  5. 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:

  1. We need to explore the entire tree to find the longest path
  2. For each node, we need to calculate the depth of its left and right subtrees
  3. DFS naturally allows us to traverse to the leaf nodes first and then bubble up the depth information
  4. As we return from recursive calls, we can compute the diameter at each node by adding the left and right depths
  5. The recursive nature of DFS perfectly matches the recursive structure of the tree
Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

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:

  1. For each node, calculate how deep we can go in its left subtree
  2. Calculate how deep we can go in its right subtree
  3. The diameter through this node = left depth + right depth
  4. 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:

  1. 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
  2. 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, return 0 (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
  3. 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 Evaluator

Example 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:

  1. Start at root (node 1):

    • First, we need to get depths from left and right subtrees
    • Call dfs(node 2) for left subtree
  2. At node 2:

    • Call dfs(node 4) for left child
  3. 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
  4. Back at node 2:

    • Left depth from node 4: l = 1
    • Now call dfs(node 5) for right child
  5. 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
  6. 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
  7. Back at root (node 1):

    • Left depth from node 2: l = 2
    • Now call dfs(node 3) for right child
  8. 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
  9. 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)

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.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Which algorithm should you use to find a node that is close to the root of the tree?


Recommended Readings

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More