Longest Univalue Path

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

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}