algoadvance

You need to find the length of the longest path in a binary tree 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.

Clarifying Questions

  1. Is it permissible for the path to only contain one node?
    • Yes, but since that means there are no edges, the length for such a path would be 0.
  2. Can the tree have only one node?
    • Yes, it can. The length of the longest univalue path in that case would be 0 since there can’t be any edges in a single-node tree.
  3. Can the values of the nodes be any integer value?
    • Yes, the values can be any integer (positive, negative, or zero).

Strategy

  1. Depth-First Search (DFS): We’ll perform a DFS traversal of the tree starting from the root. For each node, we’ll determine the longest path that passes through the node and consists of nodes with the same value.

  2. Helper Function: We need a helper function that, for a given node, returns the length of the longest univalue path ending at that node. This function will recursively check the left and right children.

  3. Update the Maximum Path Length: We’ll maintain a variable to store the maximum length of a univalue path encountered so far.

  4. Return Values: Each call to the helper function will return the length of the longest path that extends from the current node and has the same value as the current node.

Code

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

class Solution:
    def longestUnivaluePath(self, root: TreeNode) -> int:
        self.max_len = 0
        
        def dfs(node):
            if not node:
                return 0
            
            # Traverse left and right subtrees
            left_len = dfs(node.left)
            right_len = dfs(node.right)
            
            # Initialize left and right path lengths
            left_path, right_path = 0, 0
            
            # Check if the left node has the same value
            if node.left and node.left.val == node.val:
                left_path = left_len + 1
            
            # Check if the right node has the same value
            if node.right and node.right.val == node.val:
                right_path = right_len + 1
            
            # Update the maximum length found
            self.max_len = max(self.max_len, left_path + right_path)
            
            # Return the length of the longest path that extends from the current node
            return max(left_path, right_path)
        
        dfs(root)
        return self.max_len

Time Complexity

The time complexity of the given solution is O(n) where n is the number of nodes in the tree. This is because we perform a DFS which visits each node exactly once.

Space Complexity

The space complexity will be O(h) where h is the height of the tree. This accounts for the space used by the recursive stack, and in the worst case, it can be as large as the height of the tree.

Try our interview co-pilot at AlgoAdvance.com