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.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

    |5|
   /  \ 
  4    |5|
 / \     \ 
1   1    |5|

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:

1
2
3
4
5
6
7
8
9

      1
    /   \ 
  |4|   5
  / \     \ 
|4|  |4|    5

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

Solution

To solve this problem:

  • We are tasked with finding the length of the longest path in a binary tree where each node in the path has the same value.
  • This essentially means that we need to compute the longest univalue path (a path where all nodes have the same value) in the binary tree.

Now, the longest path:

  • could either pass through the root node or be entirely contained in one of the subtrees.

So,

  • At each node, we calculate two components:
    • The univalue path that passes through the left child.
    • The univalue path that passes through the right child.
  • We keep track of the longest path encountered globally.

Method 1 - DFS

Here is the recursive DFS approach:

  • For each node, calculate the longest univalue path in its left and right subtree.
    • If the current node’s value matches its left child, extend the left univalue path. Similarly, do the same for the right child.
  • Update the global maximum path (ans) at each node.
  • The length of the path is calculated as the number of edges, so we return max(left_length, right_length) for each subtree.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

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 l_len = dfs(node.left);
        int r_len = dfs(node.right);
        
        int l_path = 0, r_path = 0;
        if (node.left != null && node.left.val == node.val) {
            l_path = l_len + 1;
        }
        if (node.right != null && node.right.val == node.val) {
            r_path = r_len + 1;
        }

        ans = Math.max(ans, l_path + r_path);
        return Math.max(l_path, r_path);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def longestUnivaluePath(self, root: Optional[TreeNode]) -> int:
        ans = 0
        
        def dfs(node: Optional[TreeNode]) -> int:
            nonlocal ans
            if not node:
                return 0
            
            l_len = dfs(node.left)
            r_len = dfs(node.right)
            
            l_path = r_path = 0
            if node.left and node.left.val == node.val:
                l_path = l_len + 1
            if node.right and node.right.val == node.val:
                r_path = r_len + 1
            
            ans = max(ans, l_path + r_path)
            return max(l_path, r_path)
        
        dfs(root)
        return ans

Complexity

  • ⏰ Time complexity:  O(n). Each node of the tree is visited once, making the time complexity O(n) (linear), where n is the number of nodes.
  • 🧺 Space complexity: O(h). The space complexity depends on the depth of the recursion stack. In the worst case (skewed binary tree), it will be O(h), where h is the height of the tree.