LeetCode 543: Diameter of Binary Tree Solution in Python – A Step-by-Step Guide

What Is LeetCode 543: Diameter of Binary Tree?

In LeetCode 543: Diameter of Binary Tree, you’re given the root of a binary tree (not necessarily a BST), and your task is to find the diameter—the length of the longest path between any two nodes, measured as the number of edges. This path may or may not pass through the root. For example, in the tree [1, 2, 3, 4, 5], the diameter is 3 (path 4-2-1-3). This problem builds on LeetCode 104: Maximum Depth of Binary Tree for height computation but extends to finding the widest span.

Problem Statement

• Input: root (TreeNode)—root of a binary tree.
• Output: Integer—diameter (number of edges in longest path).
• Rules: Path length is number of edges; can be between any two nodes.

Constraints

• Number of nodes: 1 to 10⁴.
• Node values: -100 to 100.

Examples

• Input: root = [1,2,3,4,5]
• Output: 3
• Tree:
``` 1 / \ 2 3 / \ 4 5 ```
• Path: 4-2-1-3 (3 edges).
• Input: root = [1,2]
• Output: 1
• Tree:
``` 1 / 2 ```
• Path: 2-1 (1 edge).
• Input: root = [1]
• Output: 0
• Single node, no edges.

Understanding the Problem: Measuring the Widest Span

To solve LeetCode 543: Diameter of Binary Tree in Python, we need to find the longest path between any two nodes in a binary tree, counting edges. The diameter could span through the root (left height + right height) or lie entirely within a subtree. A naive approach might compute paths between all pairs (O(n²)), but with up to 10⁴ nodes, we need efficiency. Since the diameter relates to heights, traversal can optimize this. We’ll explore:

• Best Solution (DFS with Height Tracking): O(n) time, O(h) space (h = height)—fast and optimal.
• Alternative Solution (BFS with Level Tracking): O(n) time, O(w) space (w = width)—thorough but bulkier.

Let’s dive into the DFS solution with a friendly breakdown!

Best Solution: DFS with Height Tracking

Why DFS Wins

The DFS with height tracking is the best for LeetCode 543 because it computes the diameter in O(n) time and O(h) space by traversing the tree once, tracking the maximum path through each node as the sum of left and right heights, while also computing heights for subtrees. It’s like measuring the tree’s reach at each stop, keeping the widest span in sight!

How It Works

Think of this as a tree-spanning hike:

• Step 1: DFS Traversal:
• Visit each node recursively (post-order: left, right, root).
• Step 2: Compute Heights:
• Return height of each subtree (max depth + 1).
• Step 3: Track Diameter:
• At each node, diameter = left height + right height (edges through node).
• Update global max diameter.
• Step 4: Return Max:
• Final max diameter is longest path found.
• Why It Works:
• Post-order ensures heights are ready for diameter calc.
• Single pass avoids redundant traversals.

It’s like a tree-diameter surveyor!

Step-by-Step Example

Example: root = [1, 2, 3, 4, 5]

• Init: self.max_diameter = 0.
• DFS:
• Left (2):
• Left (4): No children, height = 1, diameter = 0.
• Right (5): No children, height = 1, diameter = 0.
• Root (2): Left height = 1, Right height = 1, diameter = 1+1 = 2, self.max_diameter = 2, return height = 2.
• Right (3): No children, height = 1, diameter = 0.
• Root (1): Left height = 2, Right height = 1, diameter = 2+1 = 3, self.max_diameter = 3, return height = 3.
• Result: 3 (path 4-2-1-3).

Example: root = [1, 2]

• DFS:
• Left (2): No children, height = 1, diameter = 0.
• Root (1): Left height = 1, Right height = 0, diameter = 1+0 = 1, self.max_diameter = 1.
• Result: 1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def __init__(self):
        # Step 1: Initialize max diameter
        self.max_diameter = 0

    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        # Step 2: Start DFS
        self.dfs(root)
        return self.max_diameter

    def dfs(self, node: TreeNode) -> int:
        if not node:
            return 0

        # Step 3: Compute heights of subtrees
        left_height = self.dfs(node.left)
        right_height = self.dfs(node.right)

        # Step 4: Update max diameter (path through current node)
        current_diameter = left_height + right_height
        self.max_diameter = max(self.max_diameter, current_diameter)

        # Return height of current subtree
        return max(left_height, right_height) + 1

• Line 9: Global max diameter tracker.
• Line 13: Trigger DFS, return final result.
• Lines 16-18: Base case: null node has height 0.
• Lines 21-22: Recursively get left and right heights.
• Lines 25-26: Diameter through node = left + right, update max.
• Line 29: Return height (max of children + 1).
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(h)—recursion stack (h ≤ n).

It’s like a tree-span measurer!

Alternative Solution: BFS with Level Tracking

Why an Alternative Approach?

The BFS with level tracking solution uses breadth-first search from each node to find the longest path, tracking levels in O(n) time and O(w) space (w = max width). It’s thorough but less efficient due to multiple BFS runs, making it a good alternative for BFS learners or when DFS intuition is less clear.

How It Works

Picture this as a tree-width explorer:

• Step 1: BFS from each node.
• Step 2: Track max depth (levels) to leaves.
• Step 3: Compute diameter as max path found.

It’s like a tree-level scanner!

Step-by-Step Example

Example: root = [1, 2, 3]

• BFS from 1:
• Queue: [1], level = 0.
• Children (2, 3), level = 1, max_depth = 1.
• BFS from 2: Max_depth = 1 (to 1).
• BFS from 3: Max_depth = 1 (to 1).
• Diameter: Max path through 1 = 1+1 = 2.
• Result: 2.

Code for BFS Approach

from collections import deque

class Solution:
    def diameterOfBinaryTree(self, root: TreeNode) -> int:
        if not root:
            return 0

        def bfs(node):
            if not node:
                return 0
            queue = deque([(node, 0)])
            max_depth = 0
            visited = set()

            while queue:
                curr, depth = queue.popleft()
                if curr in visited:
                    continue
                visited.add(curr)
                max_depth = max(max_depth, depth)
                if curr.left:
                    queue.append((curr.left, depth + 1))
                if curr.right:
                    queue.append((curr.right, depth + 1))
            return max_depth

        max_diameter = 0
        def traverse(node):
            nonlocal max_diameter
            if not node:
                return
            left_depth = bfs(node.left)
            right_depth = bfs(node.right)
            max_diameter = max(max_diameter, left_depth + right_depth)
            traverse(node.left)
            traverse(node.right)

        traverse(root)
        return max_diameter

• Lines 10-23: BFS computes max depth from a node.
• Lines 26-35: Traverse tree, compute diameter at each node.
• Time Complexity: O(n²)—BFS per node.
• Space Complexity: O(w)—queue size.

It’s a BFS tree measurer!

Comparing the Two Solutions

• DFS (Best):
• Pros: O(n), O(h), efficient.
• Cons: Recursive logic.
• BFS (Alternative):
• Pros: O(n²), O(w), thorough.
• Cons: Slower, more space.

DFS wins for efficiency!

Additional Examples and Edge Cases

• [1]: 0.
• [1, null, 2]: 1.
• [1, 2, 3, 4]: 3.

DFS handles them all!

Complexity Recap

• DFS: Time O(n), Space O(h).
• BFS: Time O(n²), Space O(w).

DFS’s the speed champ!

Key Takeaways

• DFS: Height tracking—learn at Python Basics!
• BFS: Level-by-level.
• Trees: Diameters are fun.
• Python: DFS or BFS, your pick!

Final Thoughts: Span That Tree!

LeetCode 543: Diameter of Binary Tree in Python is a delightful tree challenge. DFS with height tracking is your fast track, while BFS offers a thorough alternative. Want more? Try LeetCode 104: Maximum Depth or LeetCode 124: Binary Tree Maximum Path Sum. Ready to measure? Head to Solve LeetCode 543 on LeetCode and find that diameter today!