CODEWITHSUNDEEP
algorithmdata-structurestreebinary-tree
Abhishek J
Abhishek J

Reputation: 2584

Binary Tree Find number nearest and greater than the key

Say I have a balanced binary tree. I wish to search for a key k in the tree. However, if k doesn't exist in the binary tree, it should give me the next greatest number nearest to k.

For examples suppose I have these numbers [1,5,6,8,10] as keys in the tree. If I search for '7' it should return 8 and if I search for 2 it should return 5 etc.

What would have to be the modifications in the binary tree to be able to perform such a search? I want an O(log n) solution as well please.

Upvotes: 2

Views: 844

Answers (1)

Paul Hankin
Paul Hankin

Reputation: 58261

Assuming you mean "binary search tree" rather than "binary tree", you don't need any modifications to find the minimum element y in the tree such that y >= x.

search(n, x, best_so_far) ::=
    if n == nil { return best_so_far }
    if n.value == x { return x }
    if n.value > x { return search(n.left, x, min(best_so_far, n.value) }
    if n.value < x { return search(n.right, x, best_so_far) }

You would call this function as search(root, x, +infinity).

The idea is that if you're exploring the left branch at a node n, you don't need to consider anything to the right of n: n.value is larger than x, and everything to the right is larger than n.value. Similarly, if you're exploring the right branch of a node n, then you can discard everything to the left of n: n.value is smaller than x and everything to the left of n is smaller than n.value.

The code's runtime is bounded by the height of the tree, so is O(log n) if the tree is balanced.

Upvotes: 5

Related Questions