Coding Interview PatternsDiameter of Binary Tree
EasyTree Depth-First Search
Diameter of Binary Tree
Explanation & Solution
Description
Given the root of a binary tree, return the length of the diameter of the tree.
The diameter of a binary tree is the longest path between any two nodes in the tree. This path may or may not pass through the root.
The length of a path is measured by the number of edges between nodes.
Examples
Example 1:
```tree
[1, 2, 3, 4, 5]
`
Input:root = [1, 2, 3, 4, 5]
0
1
1
2
2
3
3
4
4
5
Output: 3
Explanation: The longest path is [4, 2, 1, 3] or [5, 2, 1, 3], which has length 3.
Example 2:
```tree
[1, 2]
`
Input:root = [1, 2]
0
1
1
2
Output: 1
Constraints
- The number of nodes in the tree is in the range
[1, 10⁴] -100 <= Node.val <= 100
Approach
Tree Depth-First Search pattern
1. Initialize Diameter
- Create a variable
diameter = 0 - This will store the maximum path length found during traversal
2. Define DFS Function
- Create a recursive function
dfs(node) - Purpose:
- Return height of the current subtree
- Update the diameter
3. Base Case
- If
nodeisnull: - Return
0 - Reason:
- An empty subtree has height
0
4. Traverse Left and Right
- Recursively compute:
left = dfs(node.left)right = dfs(node.right)- These represent heights of left and right subtrees
5. Compute Diameter at Current Node
- Calculate:
left + right- This represents:
- The longest path passing through this node
6. Update Global Diameter
- Compare and update:
diameter = max(diameter, left + right)- Ensures we always keep the maximum path found so far
7. Return Height to Parent
- Return:
max(left, right) + 1- Why:
- Height is the longest path from current node to a leaf
8. Start DFS from Root
- Call:
dfs(root)- This triggers traversal of the entire tree
9. Return Final Answer
- After traversal:
- Return
diameter - This is the longest path between any two nodes
Visualization
Input:
DFS Traversal[1, 2, 3, 4, 5]
output0
Press play to start DFS traversal
CurrentIn stackComplete
11 steps