Katkat
Back

Find the Longest Path of Equal-Valued Tree Nodes

GoogleSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests tree traversal techniques and dynamic programming on trees, specifically how to track path lengths across subtree boundaries using a recursive helper function.

Problem Statement

Given a binary tree represented as an array of values in level-order (breadth-first) traversal, where null represents missing nodes, find the number of nodes in the longest path where every node has the same value. The path does not need to pass through the root, but it must be connected (i.e., every node in the path must be a parent or child of another node in the path).

Input

  • root: The root node of a binary tree.

Output

  • An integer representing the maximum number of nodes in a path where all nodes have the same value.

Example 1

Input: [4, 4, 4, null, 4, 4]

  • Node 4 (root) -> left child 4 -> right child 4
  • The longest path consists of 4 connected nodes (e.g., the branch 4->4->4). Output: 4

Example 2

Input: [1, 2, 2, 2, 2] Output: 2

Constraints

  • Number of nodes: 0 to 10^5.
  • Node values: Any integer.
  • The tree structure is provided as a standard binary tree object.

Implementation

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def longest_univalue_path(root: TreeNode) -> int:
    # Implement your logic here

Hints

Hint 1

Define a helper function that returns the length of the longest univalue path starting from the current node downwards.

Hint 2

During the recursive call, compare the current node's value with its children; if a child's value matches, it can extend the path.

Hint 3

Update a global maximum variable whenever the sum of left and right extended paths (plus the current node) exceeds the current record.

Follow-up questions

  • How would you modify your solution to find the path with the largest sum of values rather than the longest number of nodes?
  • If the tree were an N-ary tree, how would the approach change regarding the recursive state?
  • Can you solve this iteratively using an explicit stack to avoid recursion depth limits in extremely skewed trees?