Build a Full Decision Tree Practice Problem

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

• Problem ID: 203
• Problem key: 203-build-a-full-decision-tree
• URL: https://datacrack.app/solve/203-build-a-full-decision-tree
• Difficulty: hard
• Topic: Decision Trees
• Module: Supervised Learning

Problem Statement

# 🧩 Build a Full Decision Tree

---

### 🎯 Goal

Use Gini impurity and repeated best splits to build a decision tree with multiple levels.

---

### 📖 Introduction

So far, you have learned how to measure Gini impurity, split a dataset, and find the best split for one node. A complete decision tree repeats that process.

1. Find the best split for the current node.
2. Create a left and right child node.
3. Find the best split inside each child that still needs one.
4. Stop when a node is pure or the tree reaches `max_depth`.

`max_depth` controls the maximum **depth** of the tree. The root node starts at depth `0`. With `max_depth=1`, the tree may split the root; with `max_depth=2`, it may also split a child node at depth `1`.

---

### 💻 Task

Implement `build_decision_tree(X, y, feature_names, max_depth)`.

Your function should:

- Find the best valid numeric split using lowest weighted child Gini.
- Build left and right child nodes recursively.
- Return a leaf when all labels at a node are the same.
- Return a leaf with the majority label when `max_depth` is reached or no valid split exists.
- If there is a tie for majority label, choose the label that appears first in the original `y`.
- Use one top-level function only. Put helpers inside `build_decision_tree`.
- Round every returned threshold to 6 decimals.

A leaf must have this shape:

```python
{"type": "leaf", "prediction": label}
```

A split node must have this shape:

```python
{
    "type": "split",
    "feature_index": ...,
    "feature_name": ...,
    "threshold": ...,
    "left": ...,
    "right": ...
}
```

---

### 📥 Input / 📤 Output

**Input**
- `X`: feature matrix
- `y`: labels
- `feature_names`: names for each feature column
- `max_depth`: maximum depth allowed for the tree

**Output**
- one nested dictionary representing the full decision tree

The returned dictionary represents the **root node** of the tree.

The big picture is:

```python
{
    "type": "split",
    "feature_index": feature_index,
    "feature_name": feature_name,
    "threshold": threshold,
    "left": left_subtree,
    "right": right_subtree
}
```

This split node asks the question:

```text
feature_name <= threshold
```

- `left_subtree` is the child node for samples that satisfy the condition.
- `right_subtree` is the child node for samples that do not satisfy the condition.

Each subtree is also a node dictionary.

A subtree can be another **split node**:

```python
{
    "type": "split",
    "feature_index": feature_index,
    "feature_name": feature_name,
    "threshold": threshold,
    "left": left_subtree,
    "right": right_subtree
}
```

or a **leaf node**:

```python
{
    "type": "leaf",
    "prediction": label
}
```

A leaf node means the tree stops and returns a prediction.

---

### 🧩 Starter Code

```python
def build_decision_tree(X, y, feature_names, max_depth):
    def gini_impurity(labels_at_node):
        # Calculate Gini impurity for the labels in one node
        pass

    def majority_label(labels_at_node):
        # Return the most common label in this node
        # If there is a tie, choose the label that appears first in the original y
        pass

    def find_best_split(row_indices):
        # Find the best split for the rows in the current node
        pass

    def build_node(row_indices, depth):
        # Build one node of the tree
        # This function calls itself to build child nodes
        pass

    return build_node(list(range(len(y))), 0)
```


---

### 💡 Example

```python
build_decision_tree(
    [[2.7], [1.3], [3.1], [1.0], [3.8], [1.5]],
    ["yes", "no", "yes", "no", "yes", "no"],
    ["size"],
    max_depth=1
)
```

Expected Output:

```python
{
    "type": "split",
    "feature_index": 0,
    "feature_name": "size",
    "threshold": 2.1,
    "left": {
        "type": "leaf",
        "prediction": "no"
    },
    "right": {
        "type": "leaf",
        "prediction": "yes"
    }
}
```