#543

Easy

auto_awesomeBinary-tree traversal and state tracking

LeetCode Problem Workspace

Diameter of Binary Tree

The Diameter of Binary Tree problem involves finding the longest path between any two nodes using tree traversal techniques.

tree depth first search binary tree

Problem Statement

Given the root of a binary tree, return the length of the diameter of the tree. The diameter is the length of the longest path between any two nodes in the tree. This path can pass through the root or not.

To calculate the diameter, you need to find the path with the maximum number of edges. A path between two nodes is defined by the edges between them. Your solution should focus on binary tree traversal and efficient state tracking to determine the diameter.

Examples

Example 1

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

Output: 3

3 is the length of the path [4,2,1,3] or [5,2,1,3].

Example 2

Input: root = [1,2]

Output: 1

Example details omitted.

Constraints

The number of nodes in the tree is in the range [1, 104].
-100 <= Node.val <= 100

Solution Approach

Depth-First Search (DFS) Traversal

Use DFS to explore each node, computing the height of the left and right subtrees. At each node, track the diameter as the sum of the left and right subtree heights.

Tracking Diameter While Traversing

As you traverse, maintain a global variable to store the maximum diameter found. At each node, calculate the diameter by summing the heights of its left and right subtrees and update the global variable accordingly.

Time Complexity Considerations

The time complexity is proportional to the number of nodes in the tree, as we visit each node once. Since each node’s height is computed in linear time, the overall complexity is O(n), where n is the number of nodes.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(n) due to the single DFS traversal, where n is the number of nodes in the tree. The space complexity is O(h), where h is the height of the tree, accounting for the recursive stack space used during DFS.

What Interviewers Usually Probe

Understand the relationship between subtree height and the diameter at each node.
Ability to optimize tree traversal to avoid redundant computations.
Demonstrate clarity in balancing between height calculation and tracking the diameter.

Common Pitfalls or Variants

Common pitfalls

Forgetting to update the global diameter variable during traversal.
Confusing the number of nodes in the path with the number of edges.
Overcomplicating the problem by considering all possible paths instead of focusing on subtree heights.

Follow-up variants

Find the diameter of a binary tree with different constraints, like skewed trees or highly unbalanced trees.
Extend the problem to return the nodes involved in the longest path.
Optimize the solution by minimizing recursion depth for extremely large trees.

FAQ

What is the diameter of a binary tree?

The diameter of a binary tree is the length of the longest path between any two nodes in the tree. This path can either pass through or not pass through the root.

How do you find the diameter of a binary tree?

The diameter can be found by performing a depth-first search (DFS), calculating the height of subtrees, and tracking the maximum diameter during traversal.

Why does the DFS approach work for this problem?

DFS works because it allows you to compute the height of each subtree while traversing the tree, which is necessary to calculate the diameter at each node.

How is the time complexity of the solution determined?

The time complexity is O(n), where n is the number of nodes in the tree, since each node is visited once during the DFS traversal.

What are common mistakes when solving the Diameter of Binary Tree problem?

Common mistakes include failing to correctly track the diameter during traversal, misunderstanding the definition of the path (edges vs. nodes), and inefficiently solving the problem by considering all paths.

terminal

Solution

Solution 1: Enumeration + DFS

We can enumerate each node of the binary tree, and for each node, calculate the maximum depth of its left and right subtrees, $\textit{l}$ and $\textit{r}$, respectively. The diameter of the node is $\textit{l} + \textit{r}$. The maximum diameter among all nodes is the diameter of the binary tree.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        def dfs(root):
            if root is None:
                return 0
            nonlocal ans
            left, right = dfs(root.left), dfs(root.right)
            ans = max(ans, left + right)
            return 1 + max(left, right)

        ans = 0
        dfs(root)
        return ans

Continue Practicing

#538 convert bst to greater tree #530 minimum absolute difference in bst #563 binary tree tilt