Frontend School

Longest Even-Valued Path to Leaf

DSA
medium

Longest Even-Valued Path to Leaf

Medium
Tree
DFS
Binary Tree
Path

Overview

In distributed systems and data processing pipelines, analyzing connectivity and properties of paths within hierarchical data structures (like dependency trees or configuration trees) is critical. For instance, identifying paths that meet specific criteria can help in optimizing data flow or pinpointing critical sequences of operations. This problem focuses on traversing a binary tree to find a path with a specific value constraint, mirroring scenarios where data attributes along a chain must conform to certain rules.

What you need to do / Task

You are given the root of a binary tree. Your task is to find the length of the longest "even-valued path to a leaf". An "even-valued path to a leaf" is defined as a path that:

  1. Starts from any node in the tree.
  2. Ends at a leaf node.
  3. Every node along this path (inclusive of the starting node and the leaf node) must have an even integer value.

The length of a path is defined as the number of nodes in that path. If no such path exists in the tree, you should return 0.

Input & output

Input:

  • root: The root node of a binary tree. Each TreeNode has an integer value val, a left child, and a right child. Both left and right can be null.

Output:

  • An integer representing the maximum length of any even-valued path to a leaf found in the tree. Return 0 if no such path exists.

Clarifications

  • An empty tree (root = null) should result in a length of 0.
  • A single node tree where the node value is even has an even-valued path to leaf of length 1.
  • A single node tree where the node value is odd has no even-valued path to leaf, so the length is 0.
  • Node values can be negative, zero, or positive. Zero is considered an even number.

Examples

1

Example 1

Input:

root = [2,4,3,6,null,null,8]

Output:

3

Note:

The longest even-valued path to a leaf is 2 -> 4 -> 6, which has a length of 3 nodes. Node 3 has an odd value, breaking any even-valued path through its branch.

2

Example 2

Input:

root = [10,20,30,null,null,40,50]

Output:

2

Note:

The path 10 -> 20 is an even-valued path to a leaf of length 2. The path 10 -> 30 -> 40 and 10 -> 30 -> 50 are not valid even-valued paths because node 30 has an odd value. Paths 40 and 50 are valid, but shorter.

3

Example 3

Input:

root = [1,2,3]

Output:

1

Note:

Node 1 has an odd value, so no even-valued path can start from it and extend downwards. Node 2 is even and a leaf, forming a valid path of length 1. Node 3 is odd, so it cannot form an even-valued path. The maximum length is 1.

Constraints

Constraints & assumptions

  • The number of nodes in the tree is between 0 and 10^4.
  • TreeNode.val is an integer between -10^9 and 10^9.
  • The tree is a standard binary tree (not necessarily a Binary Search Tree).

Out of scope

  • Tree modifications (insertions, deletions, balancing).
  • Finding paths that are not strictly downward to a leaf (e.g., paths between two arbitrary nodes).

What interviewers evaluate

  • Correctness: The solution correctly identifies the longest even-valued path to a leaf for all valid inputs, including edge cases.
  • Efficiency: The solution uses an optimal time and space complexity (e.g., O(N) time for N nodes, O(H) space for tree height H).
  • Code Structure and Readability: The code is well-organized, easy to understand, and follows good practices (e.g., clear variable names, modularity if applicable).
  • Edge Case Handling: The solution gracefully handles empty trees, single-node trees, and trees with no valid even-valued paths.

Loading editor...