Tree SHAP: Exact Feature Attribution - Quant Researcher Interview Question

Problem Description

SHAP (SHapley Additive exPlanations) values provide a unified measure of feature importance by attributing a model's prediction to individual features based on cooperative game theory. Tree SHAP efficiently computes these values for decision trees by estimating conditional expectations directly from the tree structure rather than simulating data. Task Implement a function solution(tree, x) that calculates the exact SHAP values for a given decision tree and an input feature vector x. The calcula