Pattern Matching with Data Structures in Rust

Pattern matching is a powerful feature in Rust that allows you to deconstruct data structures and execute different code branches based on their shape and content. This challenge will test your understanding of pattern matching by requiring you to implement a function that processes a nested data structure (an Option<Box<Node>>) and extracts specific information based on the node's value and children. This is useful for traversing and analyzing complex data representations like trees or graphs.

Problem Description

You are given a data structure representing a tree where each node can either have a value and zero or more children, or be empty. The structure is defined as follows:

#[derive(Debug)]
enum Node {
    Value(i32, Vec<Option<Box<Node>>>), // Value and children
    Empty,
}

Your task is to write a function sum_even_values that takes an Option<Box<Node>> as input and returns the sum of all even values found within the tree. The function should use pattern matching to traverse the tree and extract the values. The Box<Node> is used to avoid infinite recursion in the Node definition.

Key Requirements:

• The function must handle the Option type correctly, returning 0 if the tree is empty (None).
• The function must recursively traverse the tree, processing each node's value and its children.
• Only even values should be added to the sum.
• The function must correctly handle the Empty node variant.

Expected Behavior:

The function should return the sum of all even values present in the tree.

Edge Cases to Consider:

• Empty tree (None).
• Tree with only Empty nodes.
• Tree with a mix of even and odd values.
• Deeply nested trees.

Examples

Example 1:

Input: Some(Box::new(Node::Value(2, vec![Some(Box::new(Node::Value(4, vec![Some(Box::new(Node::Empty))]))], None))))
Output: 6
Explanation: The tree contains the values 2 and 4, both of which are even. Their sum is 6.

Example 2:

Input: Some(Box::new(Node::Value(1, vec![Some(Box::new(Node::Value(3, vec![Some(Box::new(Node::Empty))]))], None))))
Output: 0
Explanation: The tree contains the values 1 and 3, both of which are odd. Their sum is 0.

Example 3:

Input: Some(Box::new(Node::Value(2, vec![Some(Box::new(Node::Value(1, vec![Some(Box::new(Node::Value(4, vec![Some(Box::new(Node::Empty))]))]))]))]))
Output: 6
Explanation: The tree contains the values 2, 1, and 4. Only 2 and 4 are even, so the sum is 6.

Example 4:

Input: None
Output: 0
Explanation: The tree is empty.

Constraints

• The input tree can have a maximum depth of 10.
• Node values will be integers between -100 and 100 (inclusive).
• The function should be reasonably efficient; avoid unnecessary allocations.

Notes

• Consider using recursion to traverse the tree.
• Pattern matching is essential for handling the different node variants and the Option type.
• The Box type is used for heap allocation to avoid stack overflow issues with deeply nested trees. You don't need to explicitly manage the memory; Rust's ownership system handles that.
• Think about how to handle the Option type within the vector of children.