loading

543. Diameter of Binary Tree — Step-by-Step Visualization

easyLeetCode #543TreeDFSRecursion

Given the `root` of a binary tree, return the length of the diameter of the tree. The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root. The length of a path between two nodes is represented by the number of edges between them. **Example 1:** Input: `root = [1,2,3,4,5]` Output: `3` Explanation: `3` is the length of the path `[4,2,1,3]` or `[5,2,1,3]`. **Example 2:** Input: `root = [1,2]` Output: `1`

Algorithm Pattern

DFS Height & Diameter Tracking

Key Idea

The diameter of a tree at a particular node is the sum of the heights of its left and right subtrees. We use DFS to find the height of each subtree and keep track of the maximum sum encountered.

Step-by-Step Approach

  1. Use a global variable (or mutable reference) to track the `maxDiameter` which starts at 0.
  2. Define a recursive function `dfs` that calculates the 'height' of a node (the longest path from the node down to a leaf).
  3. For a given node, calculate the `leftHeight` and `rightHeight` by calling `dfs` on its left and right children.
  4. At every node, update the `maxDiameter` with `leftHeight + rightHeight` if this sum is greater than the current maximum.
  5. Return the height of the current node: `1 + max(leftHeight, rightHeight)` to its parent.

Common Gotchas

  • Remember that the return value of the function is the height (which is used by parents), while the 'diameter' we are seeking is actually an accumulated side effect (or updated global state).
  • Empty nodes have a height of 0 (or -1 depending on definition, but here 0 handles edge-based length correctly).

Related Problems

← All problems