Decision Tree Prediction Practice Problem

This data science coding problem helps you practice Decision Trees, decision tree prediction, and implementation skills. Read the problem statement, write your solution, and strengthen your understanding of Decision Trees.

• Problem ID: 204
• Problem key: 204-decision-tree-prediction
• URL: https://datacrack.app/solve/204-decision-tree-prediction
• Difficulty: medium
• Topic: Decision Trees
• Module: Supervised Learning

Problem Statement

# 🧩 Decision Tree Prediction

---

### 🎯 Goal

Use an existing decision tree to predict the label for one sample.

Prediction means traversing the tree from the root node to a leaf node.

---

### 📖 Introduction

A trained decision tree is a flowchart of questions.

An internal node stores a question:

> feature <= threshold

A leaf node stores a final prediction.

At prediction time, one sample starts at the root. It answers each question and moves left or right until it reaches a leaf.

Each internal node has:

- `feature`
- `threshold`
- `left`
- `right`

Each leaf node has:

- `prediction`

---

### 💻 Task

Implement `predict_decision_tree(tree, sample)`.

Your function should:

- Start at the root node.
- Keep moving while the current node is not a leaf.
- Compare `sample[feature]` with `threshold`.
- Move left if the comparison is true.
- Move right otherwise.
- Record the path taken.
- Return the final prediction and path.

---

### 📥 Input / 📤 Output

**Input**

- `tree`: a nested dictionary representing a trained decision tree.

  A split node contains:

  - `feature`: the feature used in the question
  - `threshold`: the value used for comparison
  - `left`: the child node used when the condition is true
  - `right`: the child node used when the condition is false

  A leaf node contains:
  - `prediction`: the final label returned by the tree

  Example:

  ~~~python
  tree = {
      "feature": "size",
      "threshold": 2.1,
      "left": {
          "prediction": "no"
      },
      "right": {
          "feature": "age",
          "threshold": 30,
          "left": {
              "prediction": "yes"
          },
          "right": {
              "prediction": "no"
          }
      }
  }
  ~~~


- `sample`: a dictionary containing the feature values for the sample we want to predict.

  Example:

  ~~~python
  sample = {
      "size": 1.5
  }
  ~~~

**Output**

Return a dictionary with:

- `prediction`: the final label found at the leaf node
- `path`: a list of strings showing the decisions taken from the root to the leaf

Example:

~~~python
{
    "prediction": "no",
    "path": ["size <= 2.1 -> left"]
}
~~~

---

### 🧩 Starter Code

```python
def predict_decision_tree(tree, sample):
    # Your code here
    pass
```

---

### 💡 Example 1

```python
predict_decision_tree(
    {
        "feature": "size",
        "threshold": 2.1,
        "left": {"prediction": "no"},
        "right": {"prediction": "yes"}
    },
    {"size": 1.5}
)
```

Expected Output:

```python
{
    "prediction": "no",
    "path": ["size <= 2.1 -> left"]
}
```

--- 

### 💡 Example 2

```python
predict_decision_tree(
    {
        "feature": "size",
        "threshold": 2.1,
        "left": {
            "prediction": "no"
        },
        "right": {
            "feature": "age",
            "threshold": 30,
            "left": {
                "prediction": "yes"
            },
            "right": {
                "prediction": "no"
            }
        }
    },
    {
        "size": 3.0,
        "age": 25
    }
)
```

Expected Output:

```python
{
    "prediction": "yes",
    "path": [
        "size <= 2.1 -> right",
        "age <= 30 -> left"
    ]
}
```
---

### ⚠️ Common Mistakes

- Visiting every branch instead of one path.
- Forgetting to update the current node.
- Returning the leaf dictionary instead of the prediction value.