Longest Univalue Path

Medium
1928.

Longest Univalue Path

Longest Univalue Path is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.

Given the root of a binary tree, return the length of the longest path in which every node has the same value. The path may or may not pass through the root, and it may bend at one node (go up through it from one child and down into the other).

The length of a path is the number of edges on it.

Example 1

Input
root = [5,4,5,1,1,null,5]
Output
2
Explanation
The path 5 → 5 → 5 down the right side has two edges.

Example 2

Input
root = [1,4,5,4,4,null,5]
Output
2
Explanation
The path 4 – 4 – 4 runs through the left child of the root and both its children: two edges.

Example 3

Input
root = []
Output
0
Explanation
An empty tree has no path.

Constraints

  • The number of nodes in the tree is in the range [0, 10^4]
  • -1000 <= Node.val <= 1000
  • The depth of the tree will not exceed 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for a binary tree node (provided by the judge — do not redefine it):
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var longestUnivaluePath = function(root) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Longest Univalue Path — Solution in Python, Java & C++

Longest Univalue Path solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Longest Univalue Path is a medium coding problem on depth-first search and trees, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Depth-First Search, Trees
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given the root of a binary tree, return the length of the longest path in which every node has the same value. The path may or may not pass through the root, and it may bend at one node (go up through it from one child and down into the other).

The length of a path is the number of edges on it.

Example 1

Input: root = [5,4,5,1,1,null,5]
Output: 2
Explanation: The path 5 → 5 → 5 down the right side has two edges.

Example 2

Input: root = [1,4,5,4,4,null,5]
Output: 2
Explanation: The path 4 – 4 – 4 runs through the left child of the root and both its children: two edges.

Example 3

Input: root = []
Output: 0
Explanation: An empty tree has no path.

Constraints

  • The number of nodes in the tree is in the range [0, 10^4]
  • -1000 <= Node.val <= 1000
  • The depth of the tree will not exceed 1000

Hints for Longest Univalue Path

  1. Hint 1

    Every path has one highest node. At that node, the path is an arm going down the left plus an arm going down the right.

  2. Hint 2

    Compute, for every node, the longest downward arm of equal values starting there. A child extends the arm only if its value equals the node's.

  3. Hint 3

    In one post-order DFS: return the longer arm to the parent, but update the global answer with the sum of both arms.

How to solve Longest Univalue Path

Like the diameter of a tree, but an edge only counts when both its ends hold the same value. A post-order DFS returns, for each node, the longest single downward arm of equal values, and combines the two arms at the node to try the bent path.

Approach

  1. arm(node): return 0 for null; otherwise compute l = arm(left) and r = arm(right) first.
  2. al = l + 1 if the left child exists and has the same value as node, else 0; ar likewise on the right.
  3. Update best = max(best, al + ar) — the path that bends at node.
  4. Return max(al, ar): a path continuing upward can use only one side.

Why it works

Any univalue path has a unique topmost node, and from it the path is two downward arms of that value (either possibly empty). al and ar are exactly the longest such arms, so al + ar is the longest path topped at that node, and the maximum over all nodes is the answer.

Complexity

  • Time — O(n)
  • Space — O(h) for the recursion

Pitfalls

  • Count edges, not nodes — a single node is a path of length 0.
  • Recurse into a child even when its value differs: a longer path may lie entirely below it.
  • Return only one arm upward; returning al + ar would let a path fork.

Reference solution

Python

from typing import Optional

def longestUnivaluePath(root: Optional[TreeNode]) -> int:
    best = 0

    def arm(node):
        nonlocal best
        if node is None:
            return 0
        l = arm(node.left)
        r = arm(node.right)
        al = l + 1 if node.left is not None and node.left.val == node.val else 0
        ar = r + 1 if node.right is not None and node.right.val == node.val else 0
        best = max(best, al + ar)
        return max(al, ar)

    arm(root)
    return best

Java

public static int longestUnivaluePath(TreeNode root) {
    int[] best = new int[1];
    arm(root, best);
    return best[0];
}

static int arm(TreeNode node, int[] best) {
    if (node == null) return 0;
    int l = arm(node.left, best), r = arm(node.right, best);
    int al = node.left != null && node.left.val == node.val ? l + 1 : 0;
    int ar = node.right != null && node.right.val == node.val ? r + 1 : 0;
    best[0] = Math.max(best[0], al + ar);
    return Math.max(al, ar);
}

C++

int univalueArm(TreeNode* node, int& best);

int longestUnivaluePath(TreeNode* root) {
    int best = 0;
    univalueArm(root, best);
    return best;
}

int univalueArm(TreeNode* node, int& best) {
    if (!node) return 0;
    int l = univalueArm(node->left, best), r = univalueArm(node->right, best);
    int al = node->left && node->left->val == node->val ? l + 1 : 0;
    int ar = node->right && node->right->val == node->val ? r + 1 : 0;
    best = max(best, al + ar);
    return max(al, ar);
}

JavaScript

var longestUnivaluePath = function(root) {
    var best = 0;
    var arm = function(node) {
        if (node === null) return 0;
        var l = arm(node.left), r = arm(node.right);
        var al = node.left !== null && node.left.val === node.val ? l + 1 : 0;
        var ar = node.right !== null && node.right.val === node.val ? r + 1 : 0;
        if (al + ar > best) best = al + ar;
        return Math.max(al, ar);
    };
    arm(root);
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 201 depth-first search problems · the whole catalogue

Learn the technique: Depth-First Search (DFS) · Binary Trees and Tree Traversals