Longest Univalue Path in Binary Tree

The problem asks for the longest path in a binary tree where all nodes have the same value. We want the maximum number of edges in such a path.

First Approach

This solution draws inspiration from path sum problems using recursive counting. The tricky part lies in handling corner cases: when the path goes from child to child, we can only compare it separately and not return it as our function result. But parent-to-child edge counts can be returned recursively.

int longestUnivaluePath(TreeNode* root) {
    if (!root) return 0;
    int m=0;
    int lr = DFS(root, root->val, 0, m);
    // Recursive start selection, m holds child-child edges, lr holds parent-child edges  
    return max(max(lr, m), longestUnivaluePath(root->left), longestUnivaluePath(root->right));
}

int DFS(TreeNode* root, int val, int depth, int &m) {
    // Return edge count when we hit bottom or values no longer match
    if (!root || root->val!=val) return depth-1;
    // Deep search left and right subtrees
    int l = DFS(root->left, val, depth+1, m);
    int r = DFS(root->right, val, depth+1, m);
    // Always save the largest child-child path edge count
    m = max(m, l+r-2*depth);
    // Return larger parent-child path
    return max(l, r);
}

Bottom-Up Recursive Counting

Can we solve this by breaking down subproblems so we don’t need separate handling for parent-to-child versus child-to-child cases? Yes. If we look at just one node, it only has child-child paths. We calculate these by adding left and right counts. When the right count is zero, the left count becomes the maximum edges going down-left from current node. Same logic applies vice versa. Bottom-up recursion ensures every node acts as starting point. When both sides are non-zero, the current node’s maximum occurs when we sum both counts.

int longestUnivaluePath(TreeNode* root) {
    if (!root) return 0;
    int m=0;
    DFS(root, m);
    return m;
}

int DFS(TreeNode* root, int &m) {
    // Recursively get edge counts from left and right subtrees
    int l=root->left ? DFS(root->left, m) : 0;
    int r=root->right ? DFS(root->right, m) : 0;
    // Values match, include this edge in count
    l = (root->left && root->left->val == root->val) ? l+1 : 0;
    r = (root->right && root->right->val == root->val) ? r+1 : 0;
    // Current node's left + right edges always represents the maximum, can't include in recursive return
    m = max(m, l+r);
    // Return only the larger of left/right counts
    return max(l, r);
}

Reflection

The initial approach wasn’t optimal since it repeatedly traversed nodes. The second approach doesn’t need to pass parent values down during deep searches. Bottom-up counting with recursive equality checks works better.

Key Insight

DFS template:

1. First recursively call to search
2. Do what the problem asks: check, count, record, etc.
3. Return results from smallest recursive subproblem

#recursion #DFS #tree