LeetCode 543: Diameter Of Binary Tree — Step-by-Step Visual Trace

#leetcode #python #algorithms #datastructures

Easy — Binary Tree | Depth-First Search | Tree | Recursion

The Problem

Find the diameter of a binary tree, which is the length of the longest path between any two nodes in the tree. The path may or may not pass through the root.

Approach

Use a recursive depth-first search to calculate the height of each subtree. At each node, update the global diameter with the sum of left and right subtree heights, which represents the longest path passing through that node.

Time: O(n) · Space: O(h)

Code

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        def height(node):
            if not node:
                return 0
            left_height = height(node.left)
            right_height = height(node.right)
            self.diameter = max(self.diameter, left_height + right_height)
            return max(left_height, right_height) + 1

        self.diameter = 0
        height(root)
        return self.diameter