# Longest Univalue Path
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-univalue-path)
Canonical: https://scaleengineer.com/dsa/problems/longest-univalue-path
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree, Binary Tree
**Companies:** [Snowflake](https://scaleengineer.com/companies/snowflake), [Zepto](https://scaleengineer.com/companies/zepto), [Sprinklr](https://scaleengineer.com/companies/sprinklr)
---
## Problem
Given the `root` of a binary tree, return _the length of the longest path, where each node in the path has the same value_. This path may or may not pass through the root.

**The length of the path** between two nodes is represented by the number of edges between them.

**Example 1:**

![](https://assets.glich.co/dsa/longest-univalue-path/image0.jpg) 

**Input:** root = [5,4,5,1,1,null,5]
**Output:** 2
**Explanation:** The shown image shows that the longest path of the same value (i.e. 5).

**Example 2:**

![](https://assets.glich.co/dsa/longest-univalue-path/image1.jpg) 

**Input:** root = [1,4,5,4,4,null,5]
**Output:** 2
**Explanation:** The shown image shows that the longest path of the same value (i.e. 4).

**Constraints:**

* The number of nodes in the tree is in the range `[0, 104]`.
* `-1000 <= Node.val <= 1000`
* The depth of the tree will not exceed `1000`.

# Approaches
## Brute Force with Apex Node Iteration
This approach systematically considers every node in the tree as the potential 'apex' or 'root' of the longest univalue path. For each node, it calculates the length of the longest univalue path that can be formed by extending downwards into its left and right subtrees. The path length for a given apex node is the sum of the lengths of these two downward paths. The overall maximum length found after checking all nodes is the result. This method is straightforward but involves redundant calculations, as the path lengths for subtrees are computed multiple times.
**Time:** O(N^2), where N is the number of nodes. The main `traverse` function visits each of the N nodes. For each node, the `pathLength` helper function is called, which may traverse the entire subtree below that node. In the worst case of a skewed tree, this leads to a quadratic number of operations. · **Space:** O(H), where H is the height of the tree, for the recursion stack. In the worst case of a skewed tree, H can be N, making the space complexity O(N).
**Pros:** Conceptually simple and easy to follow.; Breaks the problem down by considering each node independently as the path's apex.
**Cons:** Highly inefficient due to redundant computations.; The `pathLength` function is called on the same subtrees multiple times, leading to a poor time complexity.
### Explanation
The core idea is to iterate through all nodes. For each node, we find the longest univalue path starting from it and going down into the left subtree, and similarly for the right subtree. The sum of these two lengths gives a candidate for the longest univalue path. We keep track of the maximum candidate found.

**Algorithm:**

- Initialize a global variable `maxLength` to 0.
- Define a main traversal function, `traverse(node)`, that visits every node in the tree (e.g., using preorder traversal).
- For each `node` visited by `traverse`:
  - Treat `node` as the apex.
  - Call a helper function, `pathLength(child, value)`, to find the length of the longest univalue path starting from `node.left` where all nodes have the value `node.val`. Let this be `leftPath`.
  - Similarly, find `rightPath` for `node.right`.
  - Update the global maximum: `maxLength = Math.max(maxLength, leftPath + rightPath)`.
  - Continue the traversal: `traverse(node.left)` and `traverse(node.right)`.
- The `pathLength(node, value)` helper function works as follows:
  - If `node` is null or `node.val` is not equal to `value`, it cannot be part of the path, so return 0.
  - Otherwise, it's a valid node. The path length is 1 (for the edge connecting to this node) plus the maximum length of univalue paths starting from its children.
  - Return `1 + Math.max(pathLength(node.left, value), pathLength(node.right, value))`.
- The final answer is the value of `maxLength` after the traversal is complete.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxLength = 0;

    public int longestUnivaluePath(TreeNode root) {
        if (root == null) {
            return 0;
        }
        traverse(root);
        return maxLength;
    }

    // Traverses every node to treat it as a potential apex
    private void traverse(TreeNode node) {
        if (node == null) {
            return;
        }
        // Calculate path length with 'node' as the apex
        int leftPath = pathLength(node.left, node.val);
        int rightPath = pathLength(node.right, node.val);
        maxLength = Math.max(maxLength, leftPath + rightPath);

        // Recurse to check other nodes as potential apexes
        traverse(node.left);
        traverse(node.right);
    }

    // Calculates the length of the longest downward univalue path from 'node'
    private int pathLength(TreeNode node, int value) {
        if (node == null || node.val != value) {
            return 0;
        }
        // 1 (for the edge to this node) + longest path from its children
        return 1 + Math.max(pathLength(node.left, value), pathLength(node.right, value));
    }
}
```
### Algorithm
- Initialize a global variable `maxLength` to 0.
- Create a main function that traverses all nodes of the tree (e.g., using a preorder traversal). Let's call the traversal function `traverse(node)`.
- Inside `traverse(node)`:
  - If `node` is null, return.
  - Calculate the longest univalue path starting from `node` and going down its left side. This requires a helper function, say `pathLength(child, value)`. Call `leftPath = pathLength(node.left, node.val)`.
  - Similarly, calculate `rightPath = pathLength(node.right, node.val)`.
  - Update the global maximum: `maxLength = max(maxLength, leftPath + rightPath)`.
  - Recursively call `traverse(node.left)` and `traverse(node.right)` to check all other nodes as potential apexes.
- The helper function `pathLength(node, value)`:
  - If `node` is null or `node.val != value`, return 0.
  - Otherwise, it's a valid extension of the path. The length from this point is 1 (for the edge to this node) plus the length of the longest path from its children.
  - Return `1 + max(pathLength(node.left, value), pathLength(node.right, value))`.
- The main function `longestUnivaluePath(root)` will initialize `maxLength`, call `traverse(root)`, and return `maxLength`.

## Optimized Single-Pass Recursion
A more efficient approach is to solve the problem in a single pass using recursion. We can use a post-order traversal strategy. A recursive helper function is designed to serve a dual purpose: for any given node, it calculates the longest univalue path that starts at that node and goes strictly downwards (an 'arrow' path), and it returns this length to its parent. Simultaneously, it uses the arrow path lengths from its children to calculate the length of the path with the current node as the apex (by combining left and right arrows) and updates a global maximum if necessary. This avoids re-computation and achieves linear time complexity.
**Time:** O(N), where N is the number of nodes. The recursive `dfs` function visits each node exactly once. · **Space:** O(H), where H is the height of the tree, due to the recursion stack. In the worst case of a skewed tree, H equals N, leading to O(N) space. For a balanced tree, it's O(log N).
**Pros:** Optimal time complexity of O(N).; Solves the problem efficiently in a single pass over the tree.
**Cons:** The logic can be slightly more complex to understand initially, as the recursive function has a dual responsibility of returning a value and updating a global state.
### Explanation
This approach cleverly combines the calculation of two different quantities in a single recursive function. The function's return value is what the parent node needs (the length of a downward 'arrow'), while the update to the global maximum path length is computed using information from the children. This is a common pattern for tree problems where a path can 'turn' at a node.

**Algorithm:**

- Initialize an instance variable `maxLength` to 0. This will store the final answer.
- Define a recursive helper function, `dfs(node)`, that will perform a post-order traversal. This function's purpose is to return the length of the longest univalue path starting at `node` and extending downwards in a single direction (an 'arrow').
- Inside `dfs(node)`:
  - Base Case: If `node` is null, return 0 as there is no path.
  - Recursively call `dfs` on the left and right children to get the arrow lengths from them: `leftLen = dfs(node.left)` and `rightLen = dfs(node.right)`.
  - Initialize the arrow lengths starting from the current `node` as 0: `arrowLeft = 0`, `arrowRight = 0`.
  - Check if the left child can extend the univalue path. If `node.left` is not null and `node.left.val == node.val`, then `arrowLeft = 1 + leftLen`.
  - Check if the right child can extend the univalue path. If `node.right` is not null and `node.right.val == node.val`, then `arrowRight = 1 + rightLen`.
  - Update the global `maxLength`. The longest path with `node` as the apex is `arrowLeft + arrowRight`. So, `maxLength = Math.max(maxLength, arrowLeft + arrowRight)`.
  - Return the length of the longest arrow starting from `node` to its parent. This will be `Math.max(arrowLeft, arrowRight)`.
- The main function `longestUnivaluePath(root)` simply calls `dfs(root)` to start the process and then returns the final `maxLength`.

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int maxLength = 0;

    public int longestUnivaluePath(TreeNode root) {
        if (root == null) {
            return 0;
        }
        dfs(root);
        return maxLength;
    }

    /**
     * Performs a post-order traversal.
     * Returns the length of the longest univalue path starting at 'node' and going downwards.
     * Updates the global 'maxLength' with the longest path found so far (which could be centered at 'node').
     */
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

        // Recursively get the arrow lengths from children
        int leftArrowFromChild = dfs(node.left);
        int rightArrowFromChild = dfs(node.right);

        // Calculate arrow lengths extending from the current node
        int arrowLeft = 0;
        int arrowRight = 0;

        if (node.left != null && node.left.val == node.val) {
            arrowLeft = 1 + leftArrowFromChild;
        }
        if (node.right != null && node.right.val == node.val) {
            arrowRight = 1 + rightArrowFromChild;
        }

        // Update the overall maximum path length. This path is centered at the current node.
        maxLength = Math.max(maxLength, arrowLeft + arrowRight);

        // Return the length of the longest single arrow path for the parent node to use.
        return Math.max(arrowLeft, arrowRight);
    }
}
```
### Algorithm
- Initialize an instance variable `maxLength` to 0. This will store the final answer.
- Define a recursive helper function, `dfs(node)`, that will perform a post-order traversal. This function's purpose is to return the length of the longest univalue path starting at `node` and extending downwards in a single direction (an 'arrow').
- Inside `dfs(node)`:
  - Base Case: If `node` is null, return 0 as there is no path.
  - Recursively call `dfs` on the left and right children to get the arrow lengths from them: `leftLen = dfs(node.left)` and `rightLen = dfs(node.right)`.
  - Initialize the arrow lengths starting from the current `node` as 0: `arrowLeft = 0`, `arrowRight = 0`.
  - Check if the left child can extend the univalue path. If `node.left` is not null and `node.left.val == node.val`, then `arrowLeft = 1 + leftLen`.
  - Check if the right child can extend the univalue path. If `node.right` is not null and `node.right.val == node.val`, then `arrowRight = 1 + rightLen`.
  - Update the global `maxLength`. The longest path with `node` as the apex is `arrowLeft + arrowRight`. So, `maxLength = Math.max(maxLength, arrowLeft + arrowRight)`.
  - Return the length of the longest arrow starting from `node` to its parent. This will be `Math.max(arrowLeft, arrowRight)`.
- The main function `longestUnivaluePath(root)` simply calls `dfs(root)` to start the process and then returns the final `maxLength`.

# Solutions
### Java

```java
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private int ans ; public int longestUnivaluePath ( TreeNode root ) { ans = 0 ; dfs ( root ); return ans ; } private int dfs ( TreeNode root ) { if ( root == null ) { return 0 ; } int left = dfs ( root . left ); int right = dfs ( root . right ); left = root . left != null && root . left . val == root . val ? left + 1 : 0 ; right = root . right != null && root . right . val == root . val ? right + 1 : 0 ; ans = Math . max ( ans , left + right ); return Math . max ( left , right ); } }
```

### JavaScript

```javascript
/** * Definition for a binary tree node. * 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) {
    let ans = 0;
    let dfs = function (root) {
      if (!root) {
        return 0;
      }
      let left = dfs(root.left),
        right = dfs(root.right);
      left = root.left?.val == root.val ? left + 1 : 0;
      right = root.right?.val == root.val ? right + 1 : 0;
      ans = Math.max(ans, left + right);
      return Math.max(left, right);
    };
    dfs(root);
    return ans;
  };

```

### CPP

```cpp
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int ans ; int longestUnivaluePath ( TreeNode * root ) { ans = 0 ; dfs ( root ); return ans ; } int dfs ( TreeNode * root ) { if ( ! root ) return 0 ; int left = dfs ( root -> left ), right = dfs ( root -> right ); left = root -> left && root -> left -> val == root -> val ? left + 1 : 0 ; right = root -> right && root -> right -> val == root -> val ? right + 1 : 0 ; ans = max ( ans , left + right ); return max ( left , right ); } };
```

### Python

```python
# Definition for a binary tree node. # class 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 : def dfs ( root ): if root is None : return 0 left , right = dfs ( root . left ), dfs ( root . right ) left = left + 1 if root . left and root . left . val == root . val else 0 right = right + 1 if root . right and root . right . val == root . val else 0 nonlocal ans ans = max ( ans , left + right ) return max ( left , right ) ans = 0 dfs ( root ) return ans
```