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.

Ric

Can you share the problem link? – Callao

(You may have used a word for negation where you intended currently|and then: now. Please capitalise the first word of each sentence.) – Flushing

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.

Bridgeport

Why would a₁ added later than a₂ mean a₂ is not a descendant of a₁? In the example from the question, every value is added to the tree with existing root value 0, which occurs twice in the list of parents. – Flushing

Answer 2

You are correct that building the tree can be slow. If the tree becomes degenerate (i.e. it has long deep chains), then building the tree will take O(n²). Here is an O(n log n) approach.

Consider the tree after inserting 19 and 3:

0
 \
  \
   19
  /
 3

We can predict the parent of the following value to be inserted, x:

• if x < 0 then its parent will be 0;
• if 0 < x < 3 then its parent will be 3 (left-hand child, but that is not important);
• if 3 < x < 19 then its parent will be 3 (right-hand child);
• if 19 < x then its parent will be 19.

Let's write this visually as

values         0       3                     19
parents   (0)     (3)             (3)             (19)

When we insert 5, we look it up, print its parent (that is 3) and update our data:

values         0       3          5          19
parents   (0)     (3)       (5)        (5)        (19)

What changed?

• we inserted 5 in its sorted place (between 3 and 19);
• we changed 3 to 5 in the corresponding parents position;
• we inserted another 5 next to the first one.

You can think of the top line as keys and the bottom line as values/payload. So basically you need a structure that allows O(log n) insertions and look ups. I personally like skip lists for the job, but any form of balanced trees will also work.

Malraux

Answer 3

While inserting a node in a BST, either of the following two can happen:

1. The new node is the left child of the smallest node larger than itself
2. The new node is the right child of the largest node smaller than or equal to itself

In order to find the smallest number that is larger than a given number, we can maintain a sorted container and perform binary search, which takes O(logn). So this following implementation is of time complexity O(nlogn), where n is the number of nodes in the tree.

#include <iostream>
#include <set>
#include <string>
#include <unordered_set>


int main(int argc, char* argv[]) {
  constexpr int kRoot = 0;

  std::set<int> numbers;
  std::unordered_set<int> left_occupied_numbers;
  numbers.insert(kRoot);

  int num_input, current;
  std::cin >> num_input;

  for (int i = 0; i < num_input; ++i) {
    std::cin >> current;
    // upper_bound will provide the smallest number that is
    // strictly greater to than the current number.
    auto it = numbers.upper_bound(current);
    if (it != numbers.end() &&
        left_occupied_numbers.find(*it) == left_occupied_numbers.end()) {
      // Left child at this iterator is still empty,
      // so the current number can be inserted here.
      // Mark the left child as taken.
      left_occupied_numbers.insert(*it);
    } else {
      // Decrementing the iterator gives the largest number that is
      // smaller than (or equal to, if all number are not distinct)
      // the current number, so the current number can be inserted
      // as the right child of this number.
      --it;
    }
    // This iterator is where current number's parent is.
    std::cout << *it;
    if (i < num_input - 1) {
      std::cout << " ";
    }
    numbers.insert(current);
  }

  std::cout << std::endl;
  return 0;
}

Sample run:

> ./run
7
19 3 5 25 21 -4 2
0 19 3 19 25 0 3

Medusa