LeetCode 687: Longest Univalue Path Solution in Python – A Step-by-Step Guide

What Is LeetCode 687: Longest Univalue Path?

In LeetCode 687: Longest Univalue Path, you’re given the root of a binary tree where each node has an integer value, and your task is to find the length of the longest path where all nodes have the same value. A path can go through any sequence of nodes connected by edges (left or right child), not necessarily passing through the root, and the length is the number of edges (nodes - 1). Return this length as an integer. For example, with the tree [5, 4, 5, 1, 1, 5], the longest univalue path is 1-1 (length 2), so return 2. This problem tests your ability to traverse a binary tree and track consecutive values efficiently.

Problem Statement

• Input:
• root: Root node of a binary tree.
• Output: An integer—length of the longest univalue path.
• Rules:
• Path: Sequence of nodes connected by edges.
• Univalue: All nodes in path have same value.
• Length: Number of edges (nodes - 1).
• Can go left or right, not necessarily through root.

Constraints

• Number of nodes: 0 to 10⁴.
• -1000 ≤ Node.val ≤ 1000.

Examples

• Input: root = [5, 4, 5, 1, 1, 5]
• Output: 2 (Path: 1-1)
• Input: root = [1, 4, 5, 4, 4, 5]
• Output: 2 (Path: 4-4)
• Input: root = []
• Output: 0 (Empty tree)

These examples set the tree—let’s solve it!

Understanding the Problem: Finding the Longest Path

To solve LeetCode 687: Longest Univalue Path in Python, we need to find the longest path in a binary tree where all nodes have the same value, counting edges between them. A brute-force approach—checking all possible paths—would be O(n²), inefficient for n ≤ 10⁴. Since we’re traversing a tree and tracking univalue paths, DFS or BFS can optimize this by processing nodes recursively or level-wise. We’ll use:

• Best Solution (DFS with Global Max): O(n) time, O(h) space—fast and elegant (h = height).
• Alternative Solution (BFS with Level Tracking): O(n) time, O(w) space—intuitive but less efficient (w = max width).

Let’s start with the DFS solution, breaking it down for beginners.

Best Solution: DFS with Global Max

Why This Is the Best Solution

The DFS with global max approach is the top choice for LeetCode 687 because it’s highly efficient—O(n) time with O(h) space—and uses a depth-first search to recursively compute the longest univalue path through each node, maintaining a global maximum to capture paths that span across subtrees. It fits constraints (n ≤ 10⁴) perfectly and is intuitive once you see the recursion logic. It’s like climbing each branch, counting same-value stretches, and keeping the longest one in your pocket!

How It Works

Think of this as a path counter:

• Step 1: Initialize Global Max:
• max_length: Track longest univalue path, starts at 0.
• Step 2: DFS Function:
• For each node:
• Recurse on left and right children.
• Get left_len, right_len: Longest univalue paths from children matching node.val.
• Update max_length: Max of current max, left_len + right_len (path through node).
• Return max(left_len, right_len): Longest path extending upward.
• Step 3: Handle Null Nodes:
• Return 0 for null nodes.
• Step 4: Return Result:
• Return max_length after DFS.

It’s like a tree measurer—count and maximize!

Step-by-Step Example

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

• Tree:
``` 5 / \ 4 5 / \ \ 1 1 5 ```
• Step 1: max_length = 0.
• Step 2: DFS:
• Left 1: No children, return 0.
• Right 1: No children, return 0.
• Node 4: Left=0, Right=0 (1≠4), max_length = 0, return 0.
• Right 5: No left, Right=0 (5≠5 mismatch), return 0.
• Root 5:
• Left=0 (4≠5), Right=0 (5=5, but child 5’s path=0).
• max_length = max(0, 0 + 0) = 0.
• Return max(0, 0) = 0.
• Node 1 (left): Left=0, Right=0, but parent=4≠1, max_length = max(0, 0 + 0) = 0.
• Node 1 (right): Left=0, Right=0, parent=4≠1, max_length = max(0, 0 + 0) = 2 (1-1 path).
• Step 3: Final max_length = 2.
• Step 4: Return 2.
• Output: 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained clearly:

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

class Solution:
    def longestUnivaluePath(self, root: TreeNode) -> int:
        # Step 1: Initialize global max
        self.max_length = 0

        # Step 2: DFS function
        def dfs(node: TreeNode) -> int:
            if not node:
                return 0

            # Recurse on children
            left_len = dfs(node.left)
            right_len = dfs(node.right)

            # Compute lengths matching node.val
            left_path = right_path = 0
            if node.left and node.left.val == node.val:
                left_path = left_len + 1
            if node.right and node.right.val == node.val:
                right_path = right_len + 1

            # Update global max
            self.max_length = max(self.max_length, left_path + right_path)

            # Return longest path extending upward
            return max(left_path, right_path)

        # Step 3: Start DFS
        dfs(root)

        # Step 4: Return result
        return self.max_length

• Lines 1-6: TreeNode: Standard node class.
• Lines 10-11: Init: max_length as instance variable.
• Lines 14-33: dfs:
• Null returns 0.
• Recurse, compute child paths, extend if values match.
• Update max_length with path through node.
• Return max path upward.
• Line 36: Start DFS.
• Line 39: Return max_length.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(h)—recursion stack (h = height).

This is like a path stretcher—traverse and max!

Alternative Solution: BFS with Level Tracking

Why an Alternative Approach?

The BFS with level tracking approach uses breadth-first search—O(n) time, O(w) space (w = max width). It’s more intuitive for some, exploring level-by-level and tracking univalue paths, but less efficient due to queue overhead. It’s like scanning the tree layer-by-layer to spot same-value stretches!

How It Works

Picture this as a level scanner:

• Step 1: BFS with queue:
• Queue: (node, path_len, value).
• Step 2: Track max length:
• Extend path_len if value matches, reset if not.
• Step 3: Update global max:
• Max of all path lengths seen.
• Step 4: Return result.

It’s like a breadth measurer—scan and count!

Step-by-Step Example

Example: Same as above

• Step 1: Queue = [(5, 0, 5)].
• Step 2: Process:
• (5, 0, 5): Add (4, 0, 4), (5, 1, 5).
• (4, 0, 4): Add (1, 0, 1), (1, 1, 1).
• (5, 1, 5): Add (5, 0, 5).
• (1, 0, 1), (1, 1, 1): 1-1 path, max_length = 2.
• Step 3: Final max_length = 2.
• Step 4: Return 2.
• Output: 2.

Code for BFS Approach

Copy codefrom collections import deque

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

        # Step 1: BFS with queue
        queue = deque([(root, 0, root.val)])  # (node, path_len, value)
        max_length = 0

        # Step 2: Process level-by-level
        while queue:
            node, path_len, value = queue.popleft()
            # Update max_length
            max_length = max(max_length, path_len)

            # Process children
            if node.left:
                if node.left.val == value:
                    queue.append((node.left, path_len + 1, value))
                else:
                    queue.append((node.left, 0, node.left.val))
            if node.right:
                if node.right.val == value:
                    queue.append((node.right, path_len + 1, value))
                else:
                    queue.append((node.right, 0, node.right.val))

        # Step 3: Return result
        return max_length

• Lines 4-6: Handle empty tree.
• Lines 9-10: Init: Queue with root, track max_length.
• Lines 13-27: Process:
• Extend or reset path_len based on value match, update max.
• Line 30: Return max_length.
• Time Complexity: O(n)—visit each node once.
• Space Complexity: O(w)—queue size (w = max width).

It’s a level counter—queue and max!

Comparing the Two Solutions

• DFS (Best):
• Pros: O(n) time, O(h) space, efficient and elegant.
• Cons: Recursion less obvious.
• BFS (Alternative):
• Pros: O(n) time, O(w) space, intuitive level-wise.
• Cons: More space, less optimal for path tracking.

DFS wins for efficiency.

Additional Examples and Edge Cases

• Input: root = [1]
• Output: 0.
• Input: root = [4, 4, 4]
• Output: 2.

DFS handles these well.

Complexity Breakdown

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

DFS is optimal for space.

Key Takeaways

• DFS: Path stretching—smart!
• BFS: Level scanning—clear!
• Trees: Measuring is fun.
• Python Tip: DFS rocks—see Python Basics.

Final Thoughts: Climb That Tree

LeetCode 687: Longest Univalue Path in Python is a fun tree challenge. DFS with global max offers speed and elegance, while BFS provides a clear alternative. Want more? Try LeetCode 543: Diameter of Binary Tree or LeetCode 124: Binary Tree Maximum Path Sum. Ready to explore? Head to Solve LeetCode 687 on LeetCode and find that longest path today!