def build_forest(X, y, n_trees=20, max_depth=5, seed=0):
    rng = np.random.default_rng(seed)
    n = len(y)
    trees = []
    for _ in range(n_trees):
        idx = rng.integers(0, n, size=n)  # bootstrap resample
        tree = build_tree(X[idx], y[idx], max_depth=max_depth)
        trees.append(tree)
    return trees


def predict_forest(trees, X):
    all_preds = np.array([predict_tree(t, X) for t in trees])  # (n_trees, n)
    # majority vote per example
    final = []
    for col in all_preds.T:
        values, counts = np.unique(col, return_counts=True)
        final.append(values[np.argmax(counts)])
    return np.array(final)


if __name__ == "__main__":
    rng = np.random.default_rng(1)
    n = 300
    X = rng.normal(size=(n, 2))
    y = (X[:, 0] ** 2 + X[:, 1] ** 2 < 1.5).astype(int)  # circle boundary

    split = int(0.8 * n)
    X_train, X_test = X[:split], X[split:]
    y_train, y_test = y[:split], y[split:]

    single_tree = build_tree(X_train, y_train, max_depth=5)
    tree_acc = np.mean(predict_tree(single_tree, X_test) == y_test)

    forest = build_forest(X_train, y_train, n_trees=25, max_depth=5)
    forest_acc = np.mean(predict_forest(forest, X_test) == y_test)

    print(f"Single tree accuracy: {tree_acc:.3f}")
    print(f"Random forest accuracy: {forest_acc:.3f}")
