*Bounty: 50*

*Bounty: 50*

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 pointfor [a node]

yat time i to be the minimum-depth nodezin the BSTTsuch that the_{i}pathfrom

zto the root ofTincludes a node from the_{i}left regionofyand a node from theright regionofy.

with

Define the *

left regionof [a node]yto consist ofyitself plus all nodes

iny’s left subtree.

Define theright regionof [a node]yto consist of all nodes iny’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.