searching a binary search tree for parents efficiently

Question

I'm trying to solve the following problem:

at first we have a bst with root 0 and nothing else. not we add n given numbers like a which:

not for instance we start to add n = 7 numbers to the tree:
19 3 5 25 21 -4 2
after adding all the numbers,the goal is to find the parent of each node in the order they were added:
0 19 3 19 25 0 3

My first approach was to build the tree while adding the nodes and print the parent at the same time:

    private static TreeNode treeInsert(TreeNode root, TreeNode newNode) {
    TreeNode y = null;
    TreeNode x = root;
    while (x != null) {
        y = x;
        if (newNode.key < x.key) x = x.left;
        else x = x.right;

    }
    newNode.parent = y;

    if (y == null) root = newNode;
    else if (newNode.key < y.key) y.left = newNode;
    else y.right = newNode;

    return newNode;

}

and this auxiliary class:

class TreeNode {
    TreeNode left;
    TreeNode right;
    TreeNode parent;
    int key;

   public TreeNode(int key) {
        this.key = key;

   }

so I can find the parent.The problem here is this algorithm is to slow! if the given numbers are too many and if we consider the tree is unbalanced then it might take forever to add new nodes. The time limit on this problem is 1 and because of the reasons I mentioned I'm exceeding that limit. I cant balance the tree because the the parents change. But maybe there is a way to solve the problem without constructing a bst and just focusing on finding the parents using the numbers.

Thank you.

Answer 1

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.