This leetcode question is interesting. It is from my archives. Originally, I misunderstood and thought you could only look for paths going “down”, but obviously as illustrated the question also admits “sideways” paths, see the second example.

Curiously, I was able to adapt my solution for the simpler interpretation and extend it to work for the more complicated interpretation too! Here is the code:

class Solution(object):
    def bottomUpBuilder(self, root):
        if root is None: return
        
        self.bottomUpBuilder(root.left)
        self.bottomUpBuilder(root.right)
        
        # can we continue a path from either of our children?
        self.longestPath[root] = 0
        if root.left and root.left.val == root.val:
            lval = self.longestPath[root.left]+1
            self.longestPath[root] = lval
        if root.right and root.right.val == root.val:
            rval = self.longestPath[root.right]+1
            self.longestPath[root] = max(self.longestPath[root], rval)
            
        # Can we join a path between our two children?
        # Note, crucially, that we're using "longestPath" for our child values;
        # we can't use asJoin because that would suggest a degree-3 node in our "path".
        self.asJoin[root] = 0
        if root.left and root.right and root.left.val == root.val and root.right.val == root.val:
            self.asJoin[root] = self.longestPath[root.left] + self.longestPath[root.right] + 2
    def longestUnivaluePath(self, root):
        self.longestPath = {}
        self.asJoin = {}
        self.bottomUpBuilder(root)
        m = 0
        for r in self.asJoin:
            m = max(m, self.asJoin[r])
        for r in self.longestPath:
            m = max(m, self.longestPath[r])
        return m

Discussion

You can see that there are basically 2 maps built, not just one. The asJoin map handles the case I forgot about.

So I can see this question as a nice one-two sort of question: first solve my simpler case, and then “can you extend that to the sideways case”? Well, the key insight that allows us to extend our code is hinted at in the comments: the asJoin map is defined in terms of longestPath, we don’t want to define it recursively.

This has a nice bottom-up iteration, and some neat invariants and applications. This question, on Leetcode, also has a certified solution. What is that solution? Let’s see.

Leetcode Solution Discussion

OK, it’s a more elegant recursive formulation (maybe?), and doesn’t admit my “extension” idea. Understanding why it’s linear-time is an interesting exercise.

More trees here, more recursion here.