Longest Univalue Path - Video Solutions

Problem Overview: Given a binary tree, find the length of the longest path where every node in the path has the same value. The path can go through any node but must follow parent-child connections. The result is measured in number of edges, not nodes.

Approach 1: Depth First Search (DFS) with Global Maximum (O(n) time, O(h) space)

This approach performs a postorder traversal using Depth-First Search. For each node, recursively compute the longest same-value path extending from its left and right children. If a child has the same value as the current node, extend the path length by 1; otherwise the contribution from that child becomes 0. The key insight is that the longest path passing through a node can combine the left and right extensions, so you update a global maximum with leftPath + rightPath. The DFS function returns the longest single-direction path (either left or right) so the parent can extend it. Since every node is visited exactly once, the algorithm runs in O(n) time with recursion stack space O(h), where h is the tree height.

This method works naturally with tree recursion and is the standard optimal solution used in most editorials. It efficiently captures the idea that the best path through a node may join two matching-value branches.

Approach 2: Breadth First Search for Tracking Paths (O(n) time, O(n) space)

An alternative strategy uses Binary Tree traversal with Breadth-First Search. Traverse the tree level by level and track potential path expansions from each node whose children share the same value. For every node, examine whether the left or right child continues a univalue chain and compute path lengths while keeping a global maximum. BFS requires additional structures (queues or maps) to track intermediate path lengths for nodes, which increases memory usage to O(n).

While BFS can solve the problem, it tends to be less intuitive because the longest path may span across two subtrees and requires combining information from children. DFS naturally handles this bottom-up aggregation.

Recommended for interviews: The DFS with global maximum approach is what interviewers expect. It demonstrates strong understanding of tree recursion and postorder aggregation. Showing how each node contributes a single-direction path upward while updating a global answer proves you understand how to combine subtree results efficiently. BFS works but is rarely the preferred explanation in interviews.