BST: post-order as serialization

Q: if I backscan a post-order output (unsorted sequence), is there only a single BST we can build?

Intuitively, I think this is like fwd scanning a pre-order output so yes.

–insights
If I keep a webcam at each tree node
* During a fwd scan of pre-order output, every node’s left child is born before right child.
* During a backscan of post-order output, every node’s right child is born before left child. During the actual post-order walk, my left child is always printed before my right child.

 

For a given BST, the pre-order output is unique; the post-order output is also unique. However,

Can two BSTs produce the same pre-order output? I think impossible
Can two BSTs produce the same post-order output? I think impossible

Like the pre-order, the post-order sequence is also a serialization but only for a BST.

Advertisements

reverse post-order mirrors pre-order #diagram+Dot

For a given binTree the pre-order sequence is mirrored by the reverse-post-order sequence.

“Reverse” := “right_child then left_child”

I had an “Aha” moment when reading P 389 [[discrete mathematics]]. Insightful illustrated path-tracer diagram showing that pre-order = ABCDEFGHIJ with root as first visited, and J=right most leaf node. The reverse-post-order = JIHGFEDCBA with root as the last visited, due to post-order. Note the DOT is on the Left for both reverse-post and pre.

(https://en.wikipedia.org/wiki/Tree_traversal#Depth-first_search has standard diagrams with a DOT on the left for pre-order; post-order has dot on the right of each node)

Note any post-order curve is less intuitive less visual (than pre-order) because the curve hits a root of subtree upon leaving ! The earlier encounters are touch-n-go. The dot can reinforce this key insight. The dot can help bridge the conceptual gap.

Similarly post-order sequence is mirrored by reverse-pre-order. For the same binTree above, reverse-pre-order = AFGHJIBDEC (not mentioned in the book). Post-order = CEDBIJHGFA, as printed in the middle of P 389. Note root is last visited due to post-order.

0 probability ^ 0 density, 3rd look

See also the earlier post on 0 probability vs 0 density.

[[GregLawler]] P42 points out that for any continuous RV such as Z ~ N(0,1), Pr (Z = 1) = 0 i.e. zero point-probability mass. However the sum of many points Pr ( |Z| < 1 ) is not zero. It’s around 68%. This is counterintuitive since we come from a background of discrete, rather than continuous, RV.

For a continuous RV, probability density is the more useful device than probability of an event. My imprecise definition is

prob_density at point (x=1) := Pr(X falling around 1 in a narrow strip of width dx)/dx

Intuitively and graphically, the strip’s area gives the probability mass.

The sum of probabilities means integration , because we always add up the strips.

Q: So what’s the meanings of zero density _vs_ zero probability? This is tricky and important.

In discrete RV, zero probability always means “impossible outcome” but in continuous RV, zero probability could mean either
A) zero density i.e. impossible outcome, or
B) positive density but strip width = 0

Eg: if I randomly selects a tree in a park, Pr(height > 9999 meter) = 0… Case A. For Case B, Pr (height = exactly 5M)=0.

continuous 0 density at a point (A) => impossible
discrete 0 probability at a point => impossible
continuous 0 probability at a point. 0 width always true by definition. Not meaningful
continuous 0 probability over a range (due  to A) => impossible

intuitive – with PUT option, 1st look

When I read financial articles, I find PUT options harder to understand than most derivatives. Here’s my summary

–> You use a put as insurance, when you worry that underlying might fall.
–> A put insurance let’s you unload your worthless asset and cash in a reasonably high strike price

Here’s a longer version

–> You use a put insurance (on an underlying) at price $100 when you think that underlying might fall below $100. This insurance lets you “unload” your asset and cash in $100. Note most put or calls traded are OTM.

A good thing about this simplified intuitive definition is, current underlying price doesn’t matter.Specifically, it doesn’t matter whether current underlying price is below or above strike (ie in the money or out).

Q: both a short position (in the underlying) and a put holder benefits from the fall. Any difference?
A: I feel if listed puts are available, then they are preferable to holding a short position. Probably cheaper and don’t tie up lots of cash.

Q: how about the put writer?
A: (perhaps not part of the “intuitive” first lesson on puts)
A: sound byte — an “insurer” .
A: therefore they don’t want volatility.  They want underlying price to stay high or at least be stable

Simplest underlying is a stock.

compared to calls, put are more like insurance (barrier option

Compared to a call, a put is more like traditional insurance. (Barrier option is a cheaper insurance than vanilla options. Down-and-in European Put is a common barrier option.)

Having an ITM call is like a shopping _coupon_ ” buy a beer at $1 with this coupon “.
* you can resell the coupon or use as gift voucher

An OTM call (more common than ITM) is like an above-market airticket offer for those affluent travelers who need last minute booking.

For puts, Commodity puts are more intuitive than equity puts. FX options and swaptions are less intuitive. Here’s an illustration —

Suppose a farmer receives guarantee from Walmart to buy his 2019 produce at a pre-set fairly low price whenever he wants within the harvest season.

  • * OTM — pre-set price is low because Walmart is providing a “distress assistance” price
  • * farmer has to pay a “membership” for this guarantee
  • * membership can be traded
  • * put writer is typically a wholesaler like Walmart who needs to regularly source the product in bulk.
    • My friend Trevor Tang is also a put writer, who doesn’t mind receiving the underlyer

Commodity option is the most intuitive. When you write a put on wheat, you advertise to take IN wheat that’s PUT OUT by the option holder. Incidentally, the strike price is typically below the current underlier price (OTM), but the take-in-PUT-out actions happen when underlier drops below the strike.

ITM call/put are more intuitive, but OTM are more important in practice.

PCP, intuitively, +! Fwd contract

The notations C, P, F are very ambiguous. F means what? MV of an existing fwd position?

Tip — either think in terms of terminal value of pre-expiry. Don’t mix them
Tip — think of owning the underlier (or a fully-paid fwd position). The standard Fwd position’s MV and PnL are … non-intuitive and confusing to me.Tip — think in terms of change in MV. MV itself is poorly defined. See post on MktVal confusion. PnL is also confusing due to the fee paid upfront…

Tip — don’t bother with the innocent-looking details of some “fwd struck at K”. It’s not so simple, after you deal with it for 5 years, and the complexity is unneeded, when we can use a fully-paid fwd position.
Tip — either think of premium paid (and locked in) or think of pre-expiry live PnL of existing positions. Don’t mix them.
Tip — don’t bother with the premium paid in the past. That amount is just a can of worm that gives nothing but confusion. The only premium thing relevant here is the value of an advertized option.

PCP assumes 0 bid/ask and 0 commission. Let’s consider the most liquid family — Eur/Usd or SPX index. The option bid/ask is large.

For a beginner, this non-trivial concept is simplified by substituting a fixed amount of cash for the bond.
http://www.theoptionsguide.com/understanding-put-call-parity.aspx has a nice diagram to illustrate the call portfolio vs the put portfolio. When studying any payoff diagram, #1 key point to bear in mind is that the X-axis is the possible underlying asset prices at_expiration. X-axis is not time. Time is irrelevant in the PCP analysis if we use cash to substitute the bond. Now let’s focus on an intuitive illustration of the call-put parity.

(In this first exmple, let’s assume an option contract has just 1 share, rather than the 100 shares in real contracts.)

A portfolio of 1 share of IBM + 1 put at $100 (Protective put — original motivation of PUT contracts and its simplest usage.)

Suppose our PUT is deep in the money, and IBM is trading at $77. Portfolio value is simply $100, since we have the right to cash in our share at $100. When IBM trades at $111, portfolio is worth $111.This payoff is equivalent to a call (K=100)+ $100 cash. In terms of terminal MV,

   K (i.e. cash) + C = P + S (i.e. underlier, paid in full)

In this illustration, we completely avoid the (confusing) fwd or futures contract. Instead, we deal with options and underlier asset only, so the MV concept is clear.

This relation holds at expiry. By arbitrage argument, it also holds any time before maturity.
—— There’s a simpler version involving just 3 trades
* Suppose I buy an $100 ATM Put for $9 and also buy 100 IBM at the current price of $100/share.(A protective put?)
* My friend buys the $100 ATM Call also at $9. (No surprise the ATM call and put have identical valuations.)
* We both start with $10900 cash.

After the purchase, my portfolio has $0 cash + the put + the stock; my friend has $10000 cash + the call.

At expiration, Our 2 portfolios are identical. In this version, you don’t see the bond position!

—— Now let’s try to make sense of PCP with a fwd but no bond. Let’s try to simplify the fwd contract. There are many standard ways to define it. As a holder, an “K-based fwd” [5] requires me to pay a fixed price $K (eg $100) at expiry to receive the asset. No upfront payment.
pnl at expiry = S_T – K, which could be negative
pnl at a time before expiry = S – K, which could be negative
MV is … defined as same as pnl. It’s non-intuitive.

   C = P + F(K)

where C and P mean the strictly positive MV of the call/put, ignoring the premium paid, and F(K) means the +/- MV of the K-based fwd contract.

The expiration range-of-possibility graph would show the RHS is the same hockey stick as the call… same terminal payoff.

This relation holds at maturity. By arbitrage argument, it also holds any time before maturity.

[5] “K-based fwd”, denoted F(K) means an off-market fwd contract struck at K. The on-market fwd has a strike price equal to the fair fwd price. In FX, the on-market fwd contract is struck at the fwd rate.