How to make lower bound in Binary Search Tree?
-
25-10-2019 - |
Question
I made nearest lower bound when I gave some integer in Binary Search Tree
def lowerBound(x : Int) : Int = {
var t = root
var result : Int = 0
while(t.key != x) {
if(x == t.key) {
result = t.left.key
}
else{
if(x < t.key) {
t = t.left
if(t == null) {
throw new NoSuchElementException
}
else {
result = t.key
}
}
else {
t = t.right
}
}
}
result
}
I have made like that. but it doesn't print any result. T T.... is any counter example in my algorithm?
if there {2, 3, 5, 7 ,8, 10, 99} lowerBound(6) is 5.
Solution
Homework?
Just a few pointers then:
- You can only exit the loop successfully with
t.key == x
, so you cannot return successfully unless x is in the tree. Sounds wrong. - If at some point you choose to go right, then you know there is at least one value in the tree less than x. So after you have gone right at least once, there is a solution and you should not fail. That does not appear in your code.
- when you choose to go right, it is possible that there will be no data there, you should check for that.
- draw a small BST and check your ideas on the drawing, that should help a lot.
Also
- be sure of what you compute. The greatest element less than or equal to x, or strictly less than x?
- maybe you can try a recursive implementation.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow