687. Longest Univalue Path - Leetcode Solution

Code Implementation

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def longestUnivaluePath(self, root: TreeNode) -> int:
        self.ans = 0
        
        def dfs(node):
            if not node:
                return 0
            left = dfs(node.left)
            right = dfs(node.right)
            left_path = right_path = 0
            if node.left and node.left.val == node.val:
                left_path = left + 1
            if node.right and node.right.val == node.val:
                right_path = right + 1
            self.ans = max(self.ans, left_path + right_path)
            return max(left_path, right_path)
        
        dfs(root)
        return self.ans

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
public:
    int ans = 0;
    int dfs(TreeNode* node) {
        if (!node) return 0;
        int left = dfs(node->left);
        int right = dfs(node->right);
        int left_path = 0, right_path = 0;
        if (node->left && node->left->val == node->val)
            left_path = left + 1;
        if (node->right && node->right->val == node->val)
            right_path = right + 1;
        ans = std::max(ans, left_path + right_path);
        return std::max(left_path, right_path);
    }
    int longestUnivaluePath(TreeNode* root) {
        dfs(root);
        return ans;
    }
};

// Definition for a binary tree node.
public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

class Solution {
    private int ans = 0;
    public int longestUnivaluePath(TreeNode root) {
        dfs(root);
        return ans;
    }
    private int dfs(TreeNode node) {
        if (node == null) return 0;
        int left = dfs(node.left);
        int right = dfs(node.right);
        int leftPath = 0, rightPath = 0;
        if (node.left != null && node.left.val == node.val)
            leftPath = left + 1;
        if (node.right != null && node.right.val == node.val)
            rightPath = right + 1;
        ans = Math.max(ans, leftPath + rightPath);
        return Math.max(leftPath, rightPath);
    }
}

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

var longestUnivaluePath = function(root) {
    let ans = 0;
    function dfs(node) {
        if (!node) return 0;
        let left = dfs(node.left);
        let right = dfs(node.right);
        let leftPath = 0, rightPath = 0;
        if (node.left && node.left.val === node.val) {
            leftPath = left + 1;
        }
        if (node.right && node.right.val === node.val) {
            rightPath = right + 1;
        }
        ans = Math.max(ans, leftPath + rightPath);
        return Math.max(leftPath, rightPath);
    }
    dfs(root);
    return ans;
};

Problem Description

The "Longest Univalue Path" problem asks you to find the length of the longest path in a binary tree where every node in the path has the same value. The path may or may not pass through the root, but it must consist of parent-child connections (edges), not just any path between nodes.

Key constraints:

The path must be continuous through parent-child links (not arbitrary connections).
Each node’s value is an integer.
The length of the path is measured by the number of edges between nodes, not the number of nodes.
The tree can be empty (in which case the answer is 0).

Example:
Given the tree:

The longest univalue path is the two edges connecting the rightmost 5s. So, the output should be 2.

Thought Process

When approaching this problem, the first instinct might be to check every possible path in the tree to see if all nodes along the path have the same value. However, this brute-force strategy is inefficient as the number of possible paths grows rapidly with the size of the tree.

Instead, we can leverage the tree structure. Since the path must be through parent-child relationships, we can use recursion to process each node and determine the longest path of same-value nodes extending from it. For each node, we look at its left and right children. If a child has the same value, we can extend the path through that child. We then combine the results to find the longest path that passes through the node.

The key realization is that for each node, the longest univalue path passing through it is the sum of the longest left and right univalue paths (if both children have the same value as the node). We keep track of the global maximum as we traverse the tree.

Solution Approach

The optimized solution uses a depth-first search (DFS) traversal. Here’s how it works step by step:

Recursive Traversal: For each node, recursively compute the longest univalue path in the left and right subtrees.
Extend Paths: If a child exists and has the same value as the current node, extend the path from the child by one (for the edge connecting to the current node).
Combine Results: The longest path passing through the current node is the sum of the left and right extended paths. Update the global maximum if this sum is larger than any previously found.
Return Value: For the purposes of the parent call, return the maximum of the left or right path, as only one path can be extended upwards towards the parent.
Base Case: If the node is null, return 0.

We use a variable (e.g., ans) to keep track of the global maximum path length found so far.
The function is called recursively for every node in the tree.
At the end, ans contains the length of the longest univalue path (measured in edges).

Example Walkthrough

Let's walk through the example tree:

Start at the root (5). Recurse left to node 4 and right to node 5.
For node 4: Both children (1 and 1) do not match 4, so left and right univalue paths from node 4 are 0.
For right child 5 (right of root): It has a right child 5 that matches. The path from this child to its parent is 1 (edge between them).
For root 5: Left univalue path is 0 (left child is 4), right univalue path is 1 (right child is 5 and matches).
The maximum path length through the root is 1 (from root to right child to right grandchild).
However, the right subtree (5 -> 5 -> 5) gives a path length of 2 (edges), which is the longest.
The function returns 2 as the result.

Time and Space Complexity

Brute-Force Approach: Checking all possible paths would result in O(N^2) time complexity, where N is the number of nodes, due to the exponential number of paths.
Optimized DFS Approach: Each node is visited once, and work at each node is constant (O(1)), so the time complexity is O(N).
Space Complexity: The space used is O(H), where H is the height of the tree, due to the recursion stack. In the worst case (skewed tree), this could be O(N).

Summary

The Longest Univalue Path problem is elegantly solved by using a DFS traversal that computes, for each node, the longest path of same-valued nodes passing through it. By combining the left and right univalue paths at each node and keeping a global maximum, we efficiently find the answer in linear time. This approach leverages the tree's recursive nature and avoids redundant work, making it both intuitive and performant.

AlgoMap.io

Want Help Cracking FAANG?