Program to find longest even value path of a binary tree in Python

A Binary tree is one of the data structures in Python in which each element is known as a Node. Each node should have a minimum of two child nodes. These children nodes are called as left child and the right child.

The top node of the binary tree is known as the Root Node, and the nodes with no children are called Leaf Nodes. Following is the representation of the Binary Tree in Python -

      10
     /  \
    5    15
   / \     \
  2   7     20

Where,

• 10 is the root Node.
• 5 is the left child of 10.
• 15 is the right child of 10.
• 2 and 7 are the children of Node 5.
• 20 is the Leaf Node.

Creating a Binary Tree

Following is the example which creates a Binary tree in Python with 1 as the root node and 2, 3 as the child nodes -

class TreeNode:
   def __init__(self, value):
      self.value = value      # The data in the node
      self.left = None        # Left child
      self.right = None       # Right child
# Create nodes
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)		

Below is the manual representation of the above Binary Tree -

    1
   / \
  2   3

Finding the Longest Even Path of Binary Tree

The longest even path in a binary tree is the longest path such that every node along that path has an even value. A path is a sequence of connected nodes in the tree from parent to child, not necessarily from root to leaf.

The length is measured by the number of edges, but not nodes, and only nodes with even values are allowed in the path. Let's consider the following Binary Tree and explore all possible paths with only even value nodes -

        2
       / \
     10   4
         / \
        8   2
       /
      6

Following are the possible even value paths of the Binary Tree -

• 2 -> 10 --- length = 1
• 2 -> 4 --- length = 1
• 4 -> 8 -> 6 --- length = 2
• 2 -> 4 -> 8 -> 6 --- length = 3
• 4 -> 2 --- length = 1
• 2 -> 4 -> 2 --- length = 2

Among all the above possibilities longest even path of the given binary Tree is 2, 4, 8, 6 with length 3.

Example

Following is the example, in which we will find the longest even value path of a given binary tree using Python -

class TreeNode:
   def __init__(self, value):
      self.value = value
      self.left = None
      self.right = None
   
class Solution:
   def __init__(self):
      self.max_length = 0
   
   def longest_even_path(self, root):
      def dfs(node):
         if not node:
            return 0
         
         # Recur for left and right children
         left_len = dfs(node.left)
         right_len = dfs(node.right)
         
         # Only process current node if it's even
         if node.value % 2 == 0:
            left = left_len if node.left and node.left.value % 2 == 0 else 0
            right = right_len if node.right and node.right.value % 2 == 0 else 0
            
            # Update global max path length
            self.max_length = max(self.max_length, left + right)
            
            return max(left, right) + 1
         else:
            return 0
      
       dfs(root)
       return self.max_length
   
root = TreeNode(2)
root.left = TreeNode(10)
root.right = TreeNode(4)
root.right.left = TreeNode(8)
root.right.right = TreeNode(2)
root.right.left.left = TreeNode(6)

# Run the solution
sol = Solution()
length = sol.longest_even_path(root)

# Print the output
print("Longest Even Value Path Length:", length)

Below is the output of the above program -

Longest Even Value Path Length: 4