American and European option pricing with early exercise detection
Want the numbers rather than the code? The interactive binomial tree calculator prices American and European calls and puts from your own inputs, draws the tree, and shows where early exercise bites.
| Symbol | Formula | Description |
|---|---|---|
| $\Delta t$ | $T / n$ | Length of each time step |
| $u$ | $e^{\sigma\sqrt{\Delta t}}$ | Up factor |
| $d$ | $e^{-\sigma\sqrt{\Delta t}} = 1/u$ | Down factor |
| $p$ | $\dfrac{e^{(r-q)\Delta t} - d}{u - d}$ | Risk-neutral probability of an up move |
where $\sigma$ is the volatility, $r$ the risk-free rate, $q$ the continuous dividend yield, and $T$ the time to expiration.
$$S_{j,i} = S_0 \; u^{i-j} \; d^{j}$$
$i$ = time step ($0, 1, \dots, n$), $j$ = number of down moves ($0, 1, \dots, i$).
At maturity ($i = n$):
$$C_{j,n} = \max(S_{j,n} - K, \; 0) \quad \text{(call)}, \qquad P_{j,n} = \max(K - S_{j,n}, \; 0) \quad \text{(put)}$$
For earlier nodes ($i < n$):
$$V_{j,i} = e^{-r\Delta t}\Big[p \, V_{j,i+1} + (1-p) \, V_{j+1,i+1}\Big]$$
Same maturity payoff, but at each earlier node we compare continuation value with the intrinsic value:
$$V_{j,i} = \max\!\Big(e^{-r\Delta t}\big[p \, V_{j,i+1} + (1-p) \, V_{j+1,i+1}\big], \; \text{Intrinsic}_{j,i}\Big)$$
Early exercise occurs whenever the intrinsic value exceeds the continuation value.
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.patches as mpatchescrr_parameters computes the up/down factors and the risk-neutral probability. crr_stock builds the full recombining stock-price tree.
def crr_parameters(sigma, n, r, q, T):
dt = T / n
u = np.exp(sigma * np.sqrt(dt))
d = np.exp(-sigma * np.sqrt(dt))
p = (np.exp((r - q) * dt) - d) / (u - d)
return u, d, p
def crr_stock(sigma, n, r, q, S, K, T):
dt = T / n
u, d, p = crr_parameters(sigma, n, r, q, T)
smat = np.zeros((n + 1, n + 1))
for i in range(n + 1):
for j in range(i + 1):
smat[j, i] = S * u ** (i - j) * d ** j
return smatWe set the strike equal to the spot price ($K = S$) so the option is at-the-money.
S = 100.0 # Spot price
K = 100.0 # Strike price (ATM)
T = 1.0 # Time to expiry (years)
r = 0.05 # Risk-free rate
q = 0.0 # Dividend yield
sigma = 0.20 # Volatility
n = 4 # Number of time steps
u, d, p = crr_parameters(sigma, n, r, q, T)
print(f"dt = {T/n:.4f}")
print(f"u = {u:.6f}")
print(f"d = {d:.6f}")
print(f"p = {p:.6f}")
smat = crr_stock(sigma, n, r, q, S, K, T)
print(f"\nStock price tree:\n{np.round(smat, 2)}")Backward induction without early-exercise check: the value at each node is purely the discounted expected value under the risk-neutral measure.
Loop 1, Payoffs at maturity (for j in range(n+1)): We fill the last column of the option matrix (omat[:, -1]). At expiry every node $j$ has a known payoff:
$$\text{call: } \max(S_{j,n} - K,\; 0) \qquad \text{put: } \max(K - S_{j,n},\; 0)$$
$j$ runs from 0 (all ups, highest stock price) down to $n$ (all downs, lowest stock price), so each row in the last column gets its terminal payoff.
Loop 2, Backward induction (for i ... for j ...): We step backwards in time from column $i = n-1$ to $i = 0$. At each time step $i$, there are $i+1$ active nodes ($j = 0, \dots, i$). For each node $(j, i)$ the option value is the discounted risk-neutral expectation of its two children:
$$V_{j,i} = e^{-r\Delta t}\Big[p \cdot V_{j,\,i+1} \;+\; (1-p) \cdot V_{j+1,\,i+1}\Big]$$
$V_{j,\,i+1}$ is the child after an up move (same row, next column). $V_{j+1,\,i+1}$ is the child after a down move (row below, next column).
When the loops finish, omat[0, 0] holds the fair option price at $t = 0$.
def crr_european(sigma, n, r, q, S, K, T, option_type='call'):
dt = T / n
omat = np.zeros((n + 1, n + 1))
u, d, p = crr_parameters(sigma, n, r, q, T)
smat = crr_stock(sigma, n, r, q, S, K, T)
# STEP 1: PAYOFFS at MATURITY
for j in range(0, n + 1):
if option_type == 'call':
omat[j, -1] = max(smat[j, -1] - K, 0)
if option_type == 'put':
omat[j, -1] = max(K - smat[j, -1], 0)
# STEP 2: BACKWARDS INDUCTION
for i in range(n - 1, -1, -1):
for j in range(0, i + 1):
omat[j, i] = (p * omat[j, i + 1] + (1 - p) * omat[j + 1, i + 1]) * np.exp(-r * dt)
return omatomat = crr_european(sigma, n, r, q, S, K, T, option_type='call')
print(f"European Call Price: ${omat[0, 0]:.4f}")The CRR tree converges to the Black-Scholes price as $n \to \infty$. Let's compare them side by side.
from scipy.stats import norm
def bs_price(S, K, T, r, q, sigma, option_type='call'):
d1 = (np.log(S / K) + (r - q + 0.5 * sigma**2) * T) / (sigma * np.sqrt(T))
d2 = d1 - sigma * np.sqrt(T)
if option_type == 'call':
return S * np.exp(-q * T) * norm.cdf(d1) - K * np.exp(-r * T) * norm.cdf(d2)
else:
return K * np.exp(-r * T) * norm.cdf(-d2) - S * np.exp(-q * T) * norm.cdf(-d1)
bs = bs_price(S, K, T, r, q, sigma, option_type='call')
crr = omat[0, 0]
diff = crr - bs
print(f"Black-Scholes Price : ${bs:.4f}")
print(f"CRR European (n={n}) : ${crr:.4f}")
print(f"Difference : ${diff:.4f}")Same backward induction, but at every node we compare the continuation value with the intrinsic value and take the maximum. This captures the early-exercise premium.
$$E_{i,j} = \max(S_{i,j} - K,\; 0) \quad \text{(call)} \qquad E_{i,j} = \max(K - S_{i,j},\; 0) \quad \text{(put)}$$
$$C_{i,j} = e^{-r\Delta t}\Big[p \cdot V_{i+1,\,j} + (1-p) \cdot V_{i+1,\,j+1}\Big]$$
$$V_{i,j} = \max\!\Big(C_{i,j},\;\; E_{i,j}\Big)$$
Loop 1 is identical to European: Terminal payoffs are the same, since at maturity there is no difference between European and American.
Loop 2 adds the early-exercise check: The outer loop walks backwards from $i = n-1$ to $0$, and the inner loop visits each node $j = 0, \dots, i$. The key difference is the max over two quantities:
Continuation value $C_{i,j}$ is the same discounted expectation as European, representing the value of holding the option.
Intrinsic value $E_{i,j}$ is what you would get by exercising right now at node $(i, j)$.
If intrinsic > continuation, the holder exercises early at that node. This is what makes American options at least as valuable as their European counterparts.
def crr_american(sigma, n, r, q, S, K, T, option_type='call'):
dt = T / n
amat = np.zeros((n + 1, n + 1))
u, d, p = crr_parameters(sigma, n, r, q, T)
smat = crr_stock(sigma, n, r, q, S, K, T)
# STEP 1: PAYOFFS at MATURITY
for j in range(0, n + 1):
if option_type == 'call':
amat[j, -1] = max(smat[j, -1] - K, 0)
if option_type == 'put':
amat[j, -1] = max(K - smat[j, -1], 0)
# STEP 2: BACKWARDS INDUCTION with EARLY EXERCISE
for i in range(n - 1, -1, -1):
for j in range(0, i + 1):
if option_type == 'call':
amat[j, i] = max(
(p * amat[j, i + 1] + (1 - p) * amat[j + 1, i + 1]) * np.exp(-r * dt),
max(smat[j, i] - K, 0)
)
if option_type == 'put':
amat[j, i] = max(
(p * amat[j, i + 1] + (1 - p) * amat[j + 1, i + 1]) * np.exp(-r * dt),
max(K - smat[j, i], 0)
)
return amatamat = crr_american(sigma, n, r, q, S, K, T, option_type='call')
print(f"American Call Price: ${amat[0, 0]:.4f}")Each node shows: S for the stock price, C for the American call value, and S − K for the intrinsic value. Nodes where early exercise is optimal (intrinsic > continuation) are highlighted in red.
def plot_crr_tree(sigma, n, r, q, S, K, T, option_type='call'):
dt = T / n
u, d, p = crr_parameters(sigma, n, r, q, T)
smat = crr_stock(sigma, n, r, q, S, K, T)
amat = crr_american(sigma, n, r, q, S, K, T, option_type)
fig, ax = plt.subplots(1, 1, figsize=(4 * (n + 1), 3 * (n + 1)))
for i in range(n + 1):
for j in range(i + 1):
x = i
y = i - 2 * j
stock = smat[j, i]
option_val = amat[j, i]
if option_type == 'call':
intrinsic = max(stock - K, 0)
else:
intrinsic = max(K - stock, 0)
if i < n:
continuation = (p * amat[j, i + 1] + (1 - p) * amat[j + 1, i + 1]) * np.exp(-r * dt)
early_exercise = intrinsic > continuation + 1e-10 and intrinsic > 0
else:
early_exercise = False
color = '#FF6B6B' if early_exercise else '#4ECDC4'
edge_color = '#C0392B' if early_exercise else '#2C3E50'
bbox = dict(boxstyle='round,pad=0.4', facecolor=color,
edgecolor=edge_color, linewidth=2)
label = f"S={stock:.2f}\nC={option_val:.2f}\nS-K={stock - K:.2f}"
ax.text(x, y, label, ha='center', va='center',
fontsize=8, fontweight='bold', bbox=bbox)
if i < n:
x_child = i + 1
y_up = (i + 1) - 2 * j
y_down = (i + 1) - 2 * (j + 1)
ax.annotate('', xy=(x_child - 0.3, y_up),
xytext=(x + 0.3, y),
arrowprops=dict(arrowstyle='->',
color='#2C3E50', lw=1.5))
ax.annotate('', xy=(x_child - 0.3, y_down),
xytext=(x + 0.3, y),
arrowprops=dict(arrowstyle='->',
color='#2C3E50', lw=1.5))
ax.set_xlim(-0.8, n + 0.8)
ax.set_ylim(-(n + 1.5), n + 1.5)
ax.set_xticks(range(n + 1))
ax.set_xticklabels([f"t={i}" for i in range(n + 1)], fontsize=10)
ax.set_yticks([])
ax.set_title(
f"CRR American {option_type.title()} Tree "
f"(S={S}, K={K}, T={T}, n={n}, \u03c3={sigma}, r={r})",
fontsize=14, fontweight='bold')
normal_patch = mpatches.Patch(facecolor='#4ECDC4',
edgecolor='#2C3E50',
label='Continuation optimal')
exercise_patch = mpatches.Patch(facecolor='#FF6B6B',
edgecolor='#C0392B',
label='Early exercise optimal')
ax.legend(handles=[normal_patch, exercise_patch],
loc='upper left', fontsize=10)
ax.spines['top'].set_visible(False)
ax.spines['right'].set_visible(False)
ax.spines['left'].set_visible(False)
plt.tight_layout()
plt.show()
plot_crr_tree(sigma, n, r, q, S, K, T, option_type='call')