American Options on a Binomial Tree

American options turned pricing into an optimal stopping problem: at every instant, decide whether to exercise now or keep holding, and the price is the best such policy. That is elegant in the abstract — V_0 = \sup_{\tau \le T} \mathbb{E}^{\mathbb{Q}}[e^{-r\tau}\text{payoff}(S_\tau)] — and completely useless as an algorithm until you have somewhere concrete to evaluate "exercise now" against "keep holding." A multi-step tree hands you exactly that: a finite grid of nodes, each with a well-defined intrinsic value and a well-defined continuation value, at which the optimal-stopping decision becomes one extra line of arithmetic. This is how American options actually get priced on a trading floor.

One extra rule at every node

Run backward induction exactly as before, but at every node — not just at expiry — stop and compare two numbers. The continuation value is the ordinary one-step discounted q-expectation of the two nodes ahead (what you'd get by never exercising early, i.e. the European value computed so far at that node). The intrinsic value is what exercising right now, at that node's stock price, would pay out. The node's true value is the larger of the two:

V_{i,j} = \max\Bigl(\underbrace{\text{intrinsic}(S_{i,j})}_{\text{exercise now}},\ \ \underbrace{e^{-r\Delta t}\bigl(q\,V_{i+1,j+1} + (1-q)\,V_{i+1,j}\bigr)}_{\text{continuation value}}\Bigr).

Start at the leaves with the terminal payoff, exactly as for a European option.
At every interior node, compute the continuation value the usual way, then take the maximum with the intrinsic (exercise) value at that node.
Whichever node this maximum switches from "continuation wins" to "exercise wins" traces out the tree's approximation of the early-exercise boundary.
The algorithm's cost is identical to the European case — the same O(N^2) walk backward through the lattice, plus one \max per node.

That's the whole idea. Everything else on this page is watching it change an answer.

Worked example: where early exercise changes the price

Take a 2-step tree: S_0 = 50, u = 1.2, d = 0.8, and one dollar in the bank grows to R = 1.05 per step, so q = (1.05-0.8)/(1.2-0.8) = 0.625. Price an American put struck at K = 52 on a stock that pays no dividends.

The tree's prices are S_u = 60, S_d = 40, and at expiry S_{uu}=72, S_{ud}=48, S_{dd}=32, giving put payoffs 0, 4, 20. Roll backward one layer:

V_u = \max\Bigl(0,\ \tfrac{0.625\cdot 0 + 0.375\cdot 4}{1.05}\Bigr) = \max(0,\ 1.43) = 1.43,

V_d = \max\Bigl(12,\ \tfrac{0.625\cdot 4 + 0.375\cdot 20}{1.05}\Bigr) = \max(12,\ 9.52) = 12.

At node d the put is deep in the money (S_d = 40 \ll K = 52). Its continuation value is only 9.52 — but exercising right now locks in 12 in cash immediately, which is strictly better. Early exercise wins, and the node's value jumps from 9.52 to 12. Now finish the roll-back to the root:

V_0 = \max\Bigl(2,\ \tfrac{0.625\cdot 1.43 + 0.375\cdot 12}{1.05}\Bigr) = \max(2,\ 5.14) = 5.14.

Compare this with the European put on the identical tree — same u, d, q — computed by never taking the early-exercise maximum. There, node d is stuck at its continuation value 9.52, and the root works out to V_0^{\text{Euro}} = (0.625\cdot 1.43 + 0.375\cdot 9.52)/1.05 = 4.25. The two prices genuinely differ:

V_0^{\text{American}} = 5.14 \;>\; V_0^{\text{European}} = 4.25.

The gap, 0.88, is the early-exercise premium — real money a European-style pricer would leave on the table if you mistakenly used it for an American put. Step through the figure to see exactly where the "exercise now" branch takes over.

Run the identical max-comparison on a call instead of a put, on the same no-dividend tree, and the intrinsic branch never wins — you can check it node by node, but the reason is structural, not coincidental. Deep in the money, a put's continuation value gets dragged down by two forces at once: discounting shrinks the payoff you'd receive later, and a put's upside is capped (the stock can't go below zero, so there's a limit to how much further the payoff can grow), while its downside protection from further stock moves keeps eroding. A call has the mirror-image asymmetry the other way: exercising early sacrifices interest on the strike you'd otherwise defer paying, and throws away the insurance against the stock falling back below K — both costs, no offsetting benefit, so continuation always wins. This is exactly the result from American Options, now visible as an arithmetic fact at every single node rather than an abstract claim.

Check the max at every node, not just once near the end. A common bug: applying the early-exercise comparison only at the second-to-last layer (thinking "close to expiry is when it matters"). The early-exercise decision can bind at any node, including near the root on a long-dated, deep-in-the-money option — the algorithm must apply \max(\cdot,\cdot) uniformly at every interior node.
Once a node exercises, its value replaces the continuation value for everything upstream. The parent node one step back must use the corrected (post-exercise) value 12 at node d above, not the un-corrected continuation value 9.52 — otherwise the early-exercise premium silently evaporates on its way back to the root.
American ≥ European, always — extra optionality can only add value, never subtract it. If your American-tree price ever comes out below the matching European-tree price, there is a bug (most often exactly the previous mistake).