searching a binary search tree for parents efficiently

We can represent existing binary search tree by segment.

Let say, we already added:

0, 21, 10, -4

So, basically, we have those segment [-4 0][0 10][10 21]

When we add a new number x, we just need to find what is the segment that this number if falling to. Let say x = 3

So, the segment is [0 10] => we break this into [0 3][3 10]

What next is to determine what is the parent of this node. Simple, just need to keep track of what node is being added later in the segment. In this case, 10 definitely added after 0, so 10 should be the parent.

Let's say

class Segment{
    int start, end, later;
}

So, for the above sequence, we have the list of segment:

Segment (-4, 0, -4), Segment(0, 10, 10) , Segment (10, 21, 10)

In case x = 11, which falls into Segment (10, 21, 10) so parent node will also be 10.

After adding 11, we will have the list of segment:

Segment (-4, 0, -4), Segment(0, 10, 10), Segment (10, 11 , 11) , Segment (11, 21, 11)

In case that the number is not inside any segment, this case should also be simple. I will left this case for reader to figure it out.

Maintaining a balanced BST to store list of segment, and we could obtain O(n log n) solution.