543. Diameter of Binary Tree - Explanation

Description

The diameter of a binary tree is defined as the length of the longest path between any two nodes within the tree. The path does not necessarily have to pass through the root.

The length of a path between two nodes in a binary tree is the number of edges between the nodes. Note that the path can not include the same node twice.

Given the root of a binary tree root, return the diameter of the tree.

Example 1:

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

Output: 3

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

Example 2:

Input: root = [1,2,3]

Output: 2

Constraints:

1 <= number of nodes in the tree <= 100
-100 <= Node.val <= 100

Recommended Time & Space Complexity

You should aim for a solution with O(n) time and O(n) space, where n is the number of nodes in the tree.

Hint 1

The diameter of a binary tree is the maximum among the sums of the left height and right height of the nodes in the tree. Why?

Hint 2

Because the diameter of a binary tree is defined as the longest path between any two nodes in the tree. The path may or may not pass through the root. For any given node, the longest path that passes through it is the sum of the height of its left subtree and the height of its right subtree.

Hint 3

A brute force solution would be to go through every node in the tree and compute its left height and right height, returning the maximum diameter found. This would be an O(n^2) solution. Can you think of a better way? Maybe we can compute the diameter as we calculate the height of the tree? Think about what information you need from each subtree during a single traversal.

Hint 4

We can use the Depth First Search (DFS) algorithm to calculate the height of the tree. At each node, the subtrees return their respective heights (leftHeight and rightHeight). Then we calculate the diameter at that node as d = leftHeight + rightHeight. We use a global variable to update the maximum diameter as needed during the traversal.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force

Intuition

For any node in a tree, the longest path that goes through it is:

height of left subtree + height of right subtree

So to find the tree’s diameter, we check this value for every node.
We also compare it with the best diameter found in the left and right subtrees.

Algorithm

If the tree is empty → diameter is 0.
For each node:
- Compute height of its left subtree.
- Compute height of its right subtree.
- Compute diameter through that node = leftHeight + rightHeight.
Recursively find diameter of left subtree.
Recursively find diameter of right subtree.
The final diameter for this node is the maximum of:
- diameter through this node
- diameter in left subtree
- diameter in right subtree
Return that maximum.

# 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: Optional[TreeNode]) -> int:
        if not root:
            return 0

        leftHeight = self.maxHeight(root.left)
        rightHeight = self.maxHeight(root.right)
        diameter = leftHeight + rightHeight
        sub = max(self.diameterOfBinaryTree(root.left),
                  self.diameterOfBinaryTree(root.right))
        return max(diameter, sub)


    def maxHeight(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0

        return 1 + max(self.maxHeight(root.left), self.maxHeight(root.right))

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(n)$

2. Depth First Search

Intuition

The diameter of a binary tree is the longest path between any two nodes.
This path must go through some node, and at that node the path length is:

(left subtree height) + (right subtree height)

So while doing a DFS to compute heights, we can simultaneously track the
maximum left + right seen so far.
This gives the diameter in one pass without recomputing heights.

Algorithm

Use DFS to compute the height of every subtree.
For each node during DFS:
- Recursively get left height.
- Recursively get right height.
- Diameter through this node = left + right.
- Update the global answer with this diameter.
Height returned to parent = 1 + max(left, right).
After DFS finishes, the global answer contains the diameter.

This gives an O(n) time solution with a single DFS traversal.

# 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: Optional[TreeNode]) -> int:
        res = 0

        def dfs(root):
            nonlocal res

            if not root:
                return 0
            left = dfs(root.left)
            right = dfs(root.right)
            res = max(res, left + right)

            return 1 + max(left, right)

        dfs(root)
        return res

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(h)$ $O (h)$
- Best Case (balanced tree): $O(log(n))$
- Worst Case (degenerate tree): $O(n)$

Where $n$ is the number of nodes in the tree and $h$ is the height of the tree.

3. Iterative DFS

Intuition

Recursive DFS is the easiest way to compute diameter, but it uses the call stack.
We can simulate the same behavior iteratively using our own stack.

We perform a post-order traversal:

Visit left subtree
Visit right subtree
Then process the current node

For each node, we store in a map:

its height
its best diameter

After both children are processed, we can compute:

Height = 1 + max(leftHeight, rightHeight)
Diameter = max(leftHeight + rightHeight, leftDiameter, rightDiameter)

This means every node is processed exactly once.

Algorithm

Use a stack to simulate DFS.
Maintain a map storing (height, diameter) for each visited node.
For each node:
- First push its children until you reach the bottom (post-order).
- When both children are processed, pop the node:
  - Retrieve left and right heights/diameters.
  - Compute:
```
height = 1 + max(leftHeight, rightHeight)
diameter = max(leftHeight + rightHeight, leftDiameter, rightDiameter)
```
  - Save these results in the map.
The final diameter is the second value stored for the root.

# 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: Optional[TreeNode]) -> int:
        stack = [root]
        mp = {None: (0, 0)}

        while stack:
            node = stack[-1]

            if node.left and node.left not in mp:
                stack.append(node.left)
            elif node.right and node.right not in mp:
                stack.append(node.right)
            else:
                node = stack.pop()

                leftHeight, leftDiameter = mp[node.left]
                rightHeight, rightDiameter = mp[node.right]

                mp[node] = (1 + max(leftHeight, rightHeight),
                           max(leftHeight + rightHeight, leftDiameter, rightDiameter))

        return mp[root][1]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$