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

Watch It Run

Try it yourself: Open TraceLit and step through every line.

---

Built with TraceLit — the visual algorithm tracer for LeetCode practice.

---

▲ 0 ▼ 0

Comments

Post Comment