1

I'm trying to find a way a way to find the minimum positive ([0, INT_MAX)) (the largest integer) value not in the binary search tree. The tree has all positive integers. I was thinking of traversing down the left side of the tree. Then creating a struct value struct { int data; bool found; };, where I return t/f if it's the min value.

I did this by traversing the left side, and if the root->data + 1 > left->data, then return the

left->data + 1

, otherwise go right. Then if

root->data + 1 < right->data

, then return root->data + 1. Otherwise return root->data or right->data if right is not null, with the found value to be false. I also have to account for if the min value in the tree is not 0, then return 0. I'm not really sure if this is the best way to go though.

Thanks for any help.

Edit: Sorry, I wrote this last night, when I was really tired. I'm using this inside of a loop, so putting it into an array each time would take up too much time. I'm using a binary search tree, so I can do it with only 1 insertion and deletion each time through the loop, with as minimum time spent finding the min value not in the tree.

Improve this question
3
  • What is max_int? Is this some number defined by your program, or is it the maximum possible integer (i.e. std::numeric_limits<int>::max)? Commented Jan 28, 2013 at 7:50
  • 1
    A binary tree or a binary search tree? Commented Jan 28, 2013 at 9:47
  • It's a binary search tree. And max_int is actually INT_MAX, it's up to the largest possible integer. Commented Jan 28, 2013 at 17:48

2 Answers 2

Reset to default
4

Here are the steps that you can follow:

  • Declare an array of size max_int of type bool and initialize all elements with false.

    bool found[max_int] = {}; //it initializes the array with false!
//assumming `max_int` is a constant expression.
//else you can use `std::vector<bool>` or `std::vector<char>`.

  • Traverse the tree, using BFS or DFS or whatever suits you. For each value v in the tree, update the array at index v as:

    found[v] = true; //it means value `v` is found in the tree!

Once you're done. The lowest index i for which found[i] is false is the value which you're looking for. That is, i is the minimum value which is not in the tree.

Note that there is a difference between binary tree and binary search tree. My solution applies to binary-tree, though it will work for binary-search-tree also. It is just that in case of binary-search-tree, you can find a more optimal solution, for example while traversing you can ignore the branch with bigger values. I hope you can do that yourself.

Improve this answer
Sign up to request clarification or add additional context in comments.

9 Comments

"Declare an array of size max_int of type bool" - which btw doesn't work on typical 32 bit implementations if max_int is INT_MAX. The fix (other than to get a 64 bit processor) is left as an exercise for the reader...
@SteveJessop: I'm puzzled. Why would it not work if max_int is INT_MAX? @the readers, call it fix or improvement in terms of memory, one can use bit instead of bool.
Because on a typical 32 bit implementation, you cannot create an array of size INT_MAX. OK, so maybe it's only half the address space rather than all of it, and so in principle it could work. In practice OSes restrict what address ranges can be used for objects created in programs.
not really, and it depends where you're putting it. Automatic variables (the stack) are typically more restricted than static storage duration (globals) or dynamic allocations. So does what happens when your allocation is unsafe: for dynamic allocations you get an allocation failure, for automatics you get undefined behavior, for globals I can't remember what happens but worst case should be that the program fails to run, perhaps with an obscure message from the OS/loader.
Oh, appendix B of C++11 recommends that implementations should be able to create an object of size 262144 bytes. That's too small a limit to be much practical use.
|
3

Assuming your tree does not contain duplicate values, you can perform an in-order traversal of your tree. The expected value of the first visited node is 0. The expected value of each subsequent visited node is one greater than the last visited node. If you encounter a node that is different from the expected value, then the expected value is the answer to your query.

I am assuming your tree is ordered because of the way you described your traversal. If your tree is not ordered, you will need to visit each node to determine the answer, but you can ignore any value that is higher than the number of nodes in your tree.

While the above provides a linear solution for a BST, you can leverage the structure more to get a logarithmic solution on average. Assume the left and right nodes are true sub-trees, then the algorithm would be:

MinMissingValue(BST t, integer b = 0):
    if (t is empty) return b;
    if (t.root.value - b) > t.root.left.count
        return MinMissingValue(t.root.left, b)
    else
        return MinMissingValue(t.root.right, t.root.value + 1)

The algorithm relies on the notion that each sub-tree knows how many nodes it contains.

Improve this answer

6 Comments

your solutions works for binary search tree, but not binary tree
@songlj: I don't deny it. The way the asker presented his traversal led me to believe it was a sorted tree.
It's a binary search tree. It is sorted; sorry for the confusion, I wrote this last night when I was tired.
Thanks man, I've just got to implement the count. Using an RB-Tree, so the count changes.
Is there a way to do it if it has repeating roots?
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.