Skip to content

543. Diameter of Binary TreeΒΆ

Problem Link

The diameter of a binary tree is the length of the longest path between any two nodes. This path might not pass through the root, so we need to consider all possibilities.

\(diameterNode = height(leftSubTree) + height(rightSubTree)\) => for each node, we need height and maximum diameter for left and right subtree. We can compute both values together using post-order variant of DFS.

From the left and right children, we obtain their heights and diameters. The height of the current node is simply 1 + max(left_height, right_height).

The maximum diameter of the current subtree node is maximum of either:

  • Maximum diameter from left subtree
  • Maximum diameter from right subtree
  • Diameter passing through the current node, which has length left_height + right_height

This way we can calculate both height and maximum diameter for the current node in the same iteration. Finally, the diameter of the entire tree is obtained from the value returned at the root.

Pseudocode 
function helper(node):
if node is null:
return (0, 0)
(lh, ld) = helper(node.left)
(rh, rd) = helper(node.right)

height = 1 + max(lh, rh)
diameter = max(ld, rd, lh + rh)

return (height, diameter)
Runtime Complexity

Time: \(O(n)\)

Space: \(O(h)\)

class Solution:
    def _helper(self, node):
        if not node:
            return 0, 0
        left_height, left_diameter = self._helper(node.left)
        right_height, right_diameter = self._helper(node.right)
        height = 1+max(left_height, right_height)
        diameter = max(left_diameter, right_diameter, 1+left_height+right_height)
        return height, diameter

    def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
         _, diameter = self._helper(root)
         return diameter

func diameterOfBinaryTree(root *TreeNode) int {
    var _helper func(node *TreeNode) (int, int)

    _helper = func(node *TreeNode) (int, int) {
        if node == nil {
            return 0, 0
        }

        leftHeight, leftDiameter := _helper(node.Left)
        rightHeight, rightDiameter := _helper(node.Right)
        height := 1 + max(leftHeight, rightHeight)
        diameter := max(leftDiameter, rightDiameter, leftHeight+rightHeight)
        return height, diameter
    }

    _, diameter := _helper(root)
    return diameter
}