Tree Manipulation with Marked Nodes

Description

Company: Jane Street

Task Description

Given a tree data structure, implement a function to manipulate this tree to achieve the following requirements:

1. Mark specific nodes on the tree.
2. Calculate the sum of all nodes in a subtree starting from a marked node.

Tree Definition

• Each node has an integer value.
• The tree has a root node and its sub-nodes.

Required Methods

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

class Tree:
    def mark_node(self, node_id: int):
        """Marks the node with the given ID."""
        pass
    
    def calculate_sum(self, node_id: int) -> int:
        """Calculates the sum of all nodes in the subtree rooted at node_id."""
        pass

Constraints

• Node IDs are unique.
• The calculate_sum method should handle cases where the node is not found or not marked (clarify behavior, e.g., return 0 or raise error). For this task, assume we only calculate sums for valid, marked nodes.

Deliverables

• Implementation code.
• At least two complete test cases.