Longest Univalue Path

medium tree dfs

Problem

Given the root of a binary tree, return the length (in edges) of the longest path where all nodes have the same value. The path does not need to pass through the root.

Inputroot = [5,4,5,1,1,null,5]

Output2

The longest 5-path is leftmost-5 → root-5 → right-5 (2 edges).

tree (level-order, "null" for empty)

def longest_univalue_path(root):
    best = [0]
    def arm(n):
        if not n: return 0
        l = arm(n.left); r = arm(n.right)
        pl = l + 1 if n.left and n.left.val == n.val else 0
        pr = r + 1 if n.right and n.right.val == n.val else 0
        best[0] = max(best[0], pl + pr)
        return max(pl, pr)
    arm(root)
    return best[0]

function longestUnivaluePath(root) {
  let best = 0;
  (function arm(n) {
    if (!n) return 0;
    const l = arm(n.left), r = arm(n.right);
    const pl = n.left && n.left.val === n.val ? l + 1 : 0;
    const pr = n.right && n.right.val === n.val ? r + 1 : 0;
    best = Math.max(best, pl + pr);
    return Math.max(pl, pr);
  })(root);
  return best;
}

class Solution {
    int best = 0;
    public int longestUnivaluePath(TreeNode root) { arm(root); return best; }
    int arm(TreeNode n) {
        if (n == null) return 0;
        int l = arm(n.left), r = arm(n.right);
        int pl = (n.left != null && n.left.val == n.val) ? l + 1 : 0;
        int pr = (n.right != null && n.right.val == n.val) ? r + 1 : 0;
        best = Math.max(best, pl + pr);
        return Math.max(pl, pr);
    }
}

int best = 0;
int arm(TreeNode* n) {
    if (!n) return 0;
    int l = arm(n->left), r = arm(n->right);
    int pl = (n->left && n->left->val == n->val) ? l + 1 : 0;
    int pr = (n->right && n->right->val == n->val) ? r + 1 : 0;
    best = max(best, pl + pr);
    return max(pl, pr);
}
int longestUnivaluePath(TreeNode* root) { best = 0; arm(root); return best; }

Explanation

We want the longest chain of nodes that all share the same value. The catch is that the best chain might bend through a node — going down its left side and continuing down its right side — so the path does not have to be straight down.

The trick is a post-order DFS where each node reports back the longest same-value arm that hangs straight down from it. A child only extends the arm if its value equals the parent's value.

At each node we compute pl (left arm) and pr (right arm). A child counts as arm + 1 only when child.val == node.val, otherwise it contributes 0. The full path that bends through this node is pl + pr edges, and we keep the global best of all such candidates.

A node can only pass one arm up to its parent (you cannot bend twice in a straight chain), so it returns max(pl, pr).

Example: [5,4,5,1,1,null,5]. The leftmost 5 and the right 5 both match the root 5, giving arms of length 1 each. Bending through the root yields 1 + 1 = 2 edges, which is the answer.

Time: O(n) Space: O(h)