#StackBounty: #binary-search-trees #definitions Understanding the Transition points of a BST

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 point for [a node]
y at time i to be the minimum-depth node z in the BST Ti such that the path from
z to the root of Ti includes a node from the left region of y and a node from the right region of y.


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):

Transition point from the notes

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?


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

Regions of the nodes F, E, C and A

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.

The TPs and their paths

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.

Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.