Longest Univalue Path: DFS Post-Order Counting

You are given the root of a binary tree. Return the length of the longest path where every node on the path has the same value. The length of the path is measured in edges, not nodes, and the path does not need to pass through the root.

This is LeetCode 687: Longest Univalue Path, and it is a clean application of the "return one direction, track global with both" pattern. If you have solved Diameter of Binary Tree, the structure will feel familiar. The twist here is that you only extend a path through a child if the child's value matches the current node's value.

The approach: post-order DFS

The idea is to run a post-order DFS where each node computes how far it can extend a univalue path in a single direction (either left or right). At each node, you check both children. If the left child exists and has the same value as the current node, you can extend through it. Same for the right child. The longest univalue path through the current node is left_path + right_path, which you compare against a global maximum. But you can only return one direction to the parent (it cannot use a path that forks), so you return max(left_path, right_path).

The key details:

1. If a child does not exist or its value differs from the current node, the path in that direction is 0.
2. If the child's value matches, the path in that direction is whatever the child returned, plus 1 for the edge connecting them.
3. You update the global maximum with left_path + right_path (the full path through this node).
4. You return max(left_path, right_path) to the parent (the longest single-direction extension).

def longestUnivaluePath(root: TreeNode | None) -> int:
    result = 0

    def dfs(node):
        nonlocal result
        if not node:
            return 0
        left = dfs(node.left)
        right = dfs(node.right)
        left_path = left + 1 if node.left and node.left.val == node.val else 0
        right_path = right + 1 if node.right and node.right.val == node.val else 0
        result = max(result, left_path + right_path)
        return max(left_path, right_path)

    dfs(root)
    return result

Step-by-step walkthrough

Let's trace the algorithm on the tree [5, 4, 5, 1, 1, null, 5]. At each node, pay attention to whether the child values match and how that affects the path extensions.

The critical moment is Step 4. At the root (value 5), the left child has value 4, so the left path is 0. The right child has value 5 and returned 1 from its own recursion, so the right path is 1 + 1 = 2. The candidate through the root is 0 + 2 = 2, which becomes the global maximum. That is the final answer: 2 edges along the path 5, 5, 5 on the right side of the tree.

Complexity analysis

Time is O(n) because every node in the tree is visited exactly once. At each node, the work is O(1): two comparisons and a max update.

Space is O(h) where h is the height of the tree. This comes from the recursion call stack. For a balanced tree, h is O(log n). For a completely skewed tree (every node has only one child), h is O(n).

The building blocks

Post-order DFS with return values

Post-order means you process both children before processing the current node. In this problem, you need the results from the left and right subtrees before you can compute how far the univalue path extends through the current node. This is the same traversal order used in Diameter of Binary Tree and Binary Tree Maximum Path Sum. Any time the parent's answer depends on information from both children, post-order is the right choice.

Tracking a global maximum during recursion

The recursive function returns the longest single-direction univalue extension (because the parent needs a chain, not a fork). But the actual answer we want, the longest univalue path anywhere in the tree, might pass through a node using both directions. So you maintain a result variable outside the recursion and update it with left_path + right_path at every node. This "return one thing, update another" pattern is the same global-max-local-return technique from Diameter of Binary Tree. The only difference here is the value-matching condition that gates whether you extend or reset to zero.

Edge cases

• Empty tree (root is None): return 0. The DFS never runs and result stays at 0.
• Single node: return 0. There are no edges at all, so the longest path has length 0.
• All nodes have the same value: the longest univalue path is the diameter of the tree. Every edge qualifies, so the problem reduces to finding the longest path between any two nodes.
• No two adjacent nodes share a value: return 0. At every node, both left_path and right_path reset to 0, so no path extends beyond a single node.
• Skewed tree with all identical values: the path is n - 1 edges. The recursion handles this correctly because each node extends the chain by 1.
• Longest path does not pass through root: this is handled automatically. The global max is updated at every node, not just at the root.

From understanding to recall

You have traced through the solution and seen how the value-matching condition gates each path extension. You understand the post-order structure and why you return one direction but track the global max with both. It all clicks right now.

But will you remember the details in a week? Will you remember that left_path resets to 0 when the values differ, or will you accidentally carry over the child's return value regardless? Will you remember to add 1 for the connecting edge, or will you be off by one?

Spaced repetition closes that gap. You practice writing the solution from scratch at increasing intervals. Each time, you reconstruct the value comparison, the conditional extension, and the global update from memory. After a few repetitions, the pattern becomes automatic and you can produce it under interview pressure without hesitation.

The global-max-local-return pattern and the value-gated extension are reusable building blocks that apply to many tree problems. Drilling them individually is far more efficient than grinding random problems and hoping the patterns stick.

Related posts

• Diameter of Binary Tree - Same post-order DFS pattern where you track the longest path through each node
• Binary Tree Maximum Path Sum - Another tree problem using the "return one direction, track global with both" technique
• Path Sum III - Tree path counting that also requires careful handling of which paths to extend