I’m trying to understand the definition of *Transition point* of a BST, as given in Demaine, Erik D., et al. "Dynamic optimality-almost." SIAM Journal on Computing 37.1 (2007): 240-251

Define the **transition point** for [a node] *y* at time i to be the minimum-depth node *z* in the BST *T*_{i} such that the **path** from *z* to the root of *T*_{i} includes a node from the **left region** of *y* and a node from the **right region** of *y*.

with

Define the **left region* of [a node] *y* to consist of *y* itself plus all nodes in *y*’s left subtree. Define the **right region** of [a node] *y* to consist of all nodes in *y*’s right subtree

I’m having trouble understanding how a path from a node to the root can pass through both the left **and** the right subtrees of a **given node**.

Since each node forks the tree, a path (towards the root) comes either from the left or right subtree.

Also, in this picture from the notes of a Demaine’s course the transition point *Z* is drawn above the node *y* (i.e. closer to the root than *y*):

I understand that the *left region* of a node **includes the node itself** but this seems to **reduce the definition** to "the root of the right region".

Now, the right region may not even exist, an apparently that’s a minor technical flaw.

Clearly, I must be missing something with my understanding of the transition point definition.

What’s wrong with my interpretation?

## Example

For example, given the following tree

For the nodes *B*, *D*, *G*, *H*, *I* there is no definition of the transition point (because there is no right region in the first place), assuming I understood the linked answer correctly.

The left and right regions of the remaining nodes (*F*, *E*, *C* and *A*) should be these ones

With the left region in blue and the right region in red.

Now, since the path from transition point to the root **must include a node from both regions** (of a given node *y*) and since these regions’ nodes are, by construction, **at least as deep in the tree as ***y* (i.e. at the same distance from the root as *y* or farther away), the transition point cannot be above *y* (when drawn in a picture of the tree).

Finally, for a path (to the root) to cross both regions it must originate in the right region and pass through *y*.

That’s the only way I can imagine such a path. Then, since the transition point must be of minimal depth, the root of the right region seems to be the only candidate.

In the picture below the light-green arrows depict the path from the Transition point to the root. The transition point is the node close to the rounded end of the array. The dark-green stars mark the node in the left and right regions (of a given node) the path goes through.

So, in this example, the transition points should be *C*, *E*, *H*, *J*.

But I’m sure something’s off, it would be great to have the correct transition point worked out for one node of the tree in the example.