Returning node value that does not exist in binary tree in O(1)

Question

I need to return node value, that doesn't exist in binary search tree in O(1). The tree has node values from (1,2...M).

The hint was to use binary search tree and to save in every node 3 fields, that will help me.

My idea was to create a field in the root that contains all the values possible, from (1..M) and every time we insert node with a certain value, we check the extra field in the root and delete it if it exist.

last to return a value that does not exist in the tree all we have to do is to enter that field in the root and return any value in it.

Any idea? Am I right?

@user2864740 NOT a particular value,just to return a random value from [1..M] that dosn't exist in the binary search tree — aminhalloun, May 25 '14 at 07:49

score 3 · Accepted Answer · edited May 23 '17 at 12:11

Consider that each node contains these three data fields:

value: value of the node itself
left: smallest value in the consecutive range to the left of this node
right: largest value in the consecutive range to the right of this node

The left/right values form the bounds of the "non-gap" value range of descendant nodes around the node's value. To find a missing value, pick one of these end-values then pick the appropriate adjacent (i.e. +/-1) value.

Whenever a child node is inserted or deleted, the left/right of all ancestors will need to be updated - this does not change the insert/delete complexity bounds nor is it part of the "find-missing" operation. The "find-missing" operation itself has a complexity of O(1) as only the left/right of the root node (and range of all values) needs to be considered.

Consider this tree:

     +--- 4 ---+
     |         |
+--- 3         6 ---+
|                   |
1                   7

Now, start adding L<..>R values from the leaves; trivially a leaf node has the range over a single value.

       +--- 4 ---+
       |         |
  +--- 3         6 ---+
  |                   |
1<1>1               7<7>7

and added to ancestors..

       +--- 4 ---+
       |         |
  +- 3<3>3     5<6>7 -+
  |                   |
1<1>1               7<7>7

and added to ancestors..

       +- 3<4>4 -+
       |         |
  +- 3<3>3     6<6>7 -+
  |                   |
1<1>1               7<7>7

Then by looking at the root node it is known that [3, 4] is a consecutive range of values in descendant nodes which contains the nodes value. Two missing values are thus 2 (3-1) or 5 (4+1).

Now, adding a node..

       +- 3<4>7 -+
       |         |
  +- 3<3>3  +- 5<6>7 -+
  |         |         |
1<1>1     5<5>5     7<7>7

.. and two missing values are known to be 2 and 8 ..

       +----- 1<4>7 -----+
       |                 |
  +- 1<2>3 -+       +- 5<6>7 -+
  |         |       |         |
1<1>1     3<3>3   5<5>5     7<7>7

.. and now 0 (which may be out of range) and 8.

The approach of using "a field in the root that contains all the values possible" sounds like using a separate Set data-structure, which is likely missing the goal of the assignment given the hint. Furthermore, consider that a binary tree (without duplicate values) is a Set itself.

Returning node value that does not exist in binary tree in O(1)

1 Answers1