Longest Univalue Path

Med

#0641Time: 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).3 companies

Algorithms

Depth-First Search

Data structures

Tree Binary Tree

Companies

Snowflake Zepto Sprinklr

Prompt

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:

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:

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, 10⁴].
-1000 <= Node.val <= 1000
The depth of the tree will not exceed 1000.

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    int maxLength = 0;18 19    public int longestUnivaluePath(TreeNode root) {20        if (root == null) {21            return 0;22        }23        traverse(root);24        return maxLength;25    }26 27    // Traverses every node to treat it as a potential apex28    private void traverse(TreeNode node) {29        if (node == null) {30            return;31        }32        // Calculate path length with 'node' as the apex33        int leftPath = pathLength(node.left, node.val);34        int rightPath = pathLength(node.right, node.val);35        maxLength = Math.max(maxLength, leftPath + rightPath);36 37        // Recurse to check other nodes as potential apexes38        traverse(node.left);39        traverse(node.right);40    }41 42    // Calculates the length of the longest downward univalue path from 'node'43    private int pathLength(TreeNode node, int value) {44        if (node == null || node.val != value) {45            return 0;46        }47        // 1 (for the edge to this node) + longest path from its children48        return 1 + Math.max(pathLength(node.left, value), pathLength(node.right, value));49    }50}

Complexity

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).

Trade-offs

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.

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.

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.

Walkthrough

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.

1/**2 * Definition for a binary tree node.3 * public class TreeNode {4 *     int val;5 *     TreeNode left;6 *     TreeNode right;7 *     TreeNode() {}8 *     TreeNode(int val) { this.val = val; }9 *     TreeNode(int val, TreeNode left, TreeNode right) {10 *         this.val = val;11 *         this.left = left;12 *         this.right = right;13 *     }14 * }15 */16class Solution {17    int maxLength = 0;18 19    public int longestUnivaluePath(TreeNode root) {20        if (root == null) {21            return 0;22        }23        dfs(root);24        return maxLength;25    }26 27    /**28     * Performs a post-order traversal.29     * Returns the length of the longest univalue path starting at 'node' and going downwards.30     * Updates the global 'maxLength' with the longest path found so far (which could be centered at 'node').31     */32    private int dfs(TreeNode node) {33        if (node == null) {34            return 0;35        }36 37        // Recursively get the arrow lengths from children38        int leftArrowFromChild = dfs(node.left);39        int rightArrowFromChild = dfs(node.right);40 41        // Calculate arrow lengths extending from the current node42        int arrowLeft = 0;43        int arrowRight = 0;44 45        if (node.left != null && node.left.val == node.val) {46            arrowLeft = 1 + leftArrowFromChild;47        }48        if (node.right != null && node.right.val == node.val) {49            arrowRight = 1 + rightArrowFromChild;50        }51 52        // Update the overall maximum path length. This path is centered at the current node.53        maxLength = Math.max(maxLength, arrowLeft + arrowRight);54 55        // Return the length of the longest single arrow path for the parent node to use.56        return Math.max(arrowLeft, arrowRight);57    }58}

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).

Trade-offs

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.

Solutions

Solution

1/** * 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 ); } }

1/** * 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 =2  function (root) {3    let ans = 0;4    let dfs = function (root) {5      if (!root) {6        return 0;7      }8      let left = dfs(root.left),9        right = dfs(root.right);10      left = root.left?.val == root.val ? left + 1 : 0;11      right = root.right?.val == root.val ? right + 1 : 0;12      ans = Math.max(ans, left + right);13      return Math.max(left, right);14    };15    dfs(root);16    return ans;17  };

1/** * 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 ); } };

1# 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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem