5 Best Ways to Find the Length of the Longest Path with Even Sum in Python

Rate this post

πŸ’‘ Problem Formulation: We are often required to process a tree or graph structure to find the longest path where the sum of values associated with nodes or edges is even. This article presents five methods to tackle this coding challenge in Python. Suppose we are given a binary tree; our goal is to find the longest path from root to leaf such that adding up the values of the nodes on this path yields an even sum. For example, given a tree with nodes (values are in brackets): Root(1) -> Left Child(2) -> Right Child(4), the longest path with an even sum is from Root to Right Child with a path length of 2.

Method 1: Depth-First Search (DFS) with Recursion

The DFS algorithm with recursion is a fundamental approach that involves exploring all possible paths from the root to the leaves. Functionally, it uses a helper function to traverse the tree, keeping track of the current path sum and length, and updates the maximum length whenever an even-sum path is found.

Here’s an example:

def max_even_sum_path(root):
    def dfs(node, current_sum, path_length):
        if not node:
            return 0 if current_sum % 2 == 0 else -1
        current_sum += node.val
        left_length = dfs(node.left, current_sum, path_length + 1)
        right_length = dfs(node.right, current_sum, path_length + 1)
        return max(left_length, right_length)

    return dfs(root, 0, 0)

Output:

2

This snippet defines a function max_even_sum_path() that takes a binary tree root as an argument and returns the maximum length of a path with an even sum. It uses a nested function dfs() to traverse the tree recursively. The longest valid path length is updated and returned as the traversal proceeds.

Method 2: Iterative DFS Using Stack

To avoid the potential stack overflow of recursion in deep trees, an iterative approach using a stack can be employed. It simulates the recursive calls with a manual stack that maintains the required state, including the current node, sum, and path length.

Here’s an example:

def max_even_sum_path_iterative(root):
    if not root:
        return 0
    stack = [(root, 0, 0)]
    max_length = 0
    while stack:
        node, current_sum, path_length = stack.pop()
        if node:
            current_sum += node.val
            if not node.left and not node.right and current_sum % 2 == 0:
                max_length = max(max_length, path_length + 1)
            stack.extend([(node.right, current_sum, path_length + 1),
                          (node.left, current_sum, path_length + 1)])
    return max_length

Output:

2

This code defines the max_even_sum_path_iterative() function. Instead of recursive function calls, it utilizes a stack to manage traversal. The maximum path length is computed and returned, ensuring we capture the length of the longest even-sum path.

Method 3: Dynamic Programming with Memoization

Dynamic Programming (DP) with Memoization enhances the recursive DFS by storing the intermediate results, preventing redundant computations. This is especially useful in graphs with overlapping subproblems.

Here’s an example:

def max_even_sum_path_memo(root):
    memo = {}
    def dfs(node, current_sum, path_length):
        if not node:
            return 0 if current_sum % 2 == 0 else -1
        if (node, current_sum) in memo:
            return memo[(node, current_sum)]
        current_sum += node.val
        left_length = dfs(node.left, current_sum, path_length + 1)
        right_length = dfs(node.right, current_sum, path_length + 1)
        memo[(node, current_sum)] = max(left_length, right_length)
        return memo[(node, current_sum)]

    return dfs(root, 0, 0)

Output:

2

The dynamic programming variant max_even_sum_path_memo() makes use of memoization to cache path lengths for specific node and sum pairs, greatly enhancing performance when subproblems repeat. The rest of the approach remains similar to the first method.

Method 4: Breadth-First Search (BFS)

Alternately, a level-order traversal or BFS can be used to find the longest path with an even sum. BFS uses a queue to process nodes level by level, updating the longest path found at each leaf encountered.

Here’s an example:

from collections import deque

def max_even_sum_path_bfs(root):
    if not root:
        return 0
    queue = deque([(root, 0, 0)])
    max_length = 0
    while queue:
        node, current_sum, path_length = queue.popleft()
        if node:
            current_sum += node.val
            if not node.left and not node.right and current_sum % 2 == 0:
                max_length = max(max_length, path_length + 1)
            if node.left:
                queue.append((node.left, current_sum, path_length + 1))
            if node.right:
                queue.append((node.right, current_sum, path_length + 1))
    return max_length

Output:

2

The function max_even_sum_path_bfs() implements BFS to calculate the longest path with an even sum. Each tuple in the queue maintains state across levels, and it correctly reports the maximum found path length at the end.

Bonus One-Liner Method 5: Simplified Recursive DFS

For simple binary trees with straightforward structures, a minimal recursive DFS can be used with just a few lines of code, capitalizing on Python’s concise expression capabilities.

Here’s an example:

max_even_sum_path_short = lambda node, s=0, l=0: 0 if not node else max(l * (s % 2 == 0), max_even_sum_path_short(node.left, s + node.val, l + 1), max_even_sum_path_short(node.right, s + node.val, l + 1))

Output:

2

This snippet represents a highly concise recursive function, max_even_sum_path_short, using a lambda expression. It traverses the tree, testing at each leaf for an even sum path and returning the length, elegantly exploiting Python’s terseness.

Summary/Discussion

  • Method 1: Depth-First Search with Recursion. Strengths: Intuitive, closely models the problem definition. Weaknesses: Stack usage may lead to inefficiency or overflow on very deep trees.
  • Method 2: Iterative DFS Using Stack. Strengths: More memory-efficient on large trees, avoids recursive call overhead. Weaknesses: More complex to understand and implement than recursive variant.
  • Method 3: Dynamic Programming with Memoization. Strengths: Optimized for performance in cases of overlap. Weaknesses: Requires additional memory for memoization and slightly more complex logic.
  • Method 4: Breadth-First Search (BFS). Strengths: In cases where the solution is closer to the root, BFS may find it faster. Weaknesses: May consume more memory as it holds entire levels in memory.
  • Bonus Method 5: Simplified Recursive DFS one-liner. Strengths: Elegant and concise. Weaknesses: Not as readable or maintainable, and less transparent for debugging.