Find the minimum gap between two numbers in an AVL tree
- by user1656647
I have a data structures homework, that in addition to the regular AVL tree functions, I have to add a function that returns the minimum gap between any two numbers in the AVL tree (the nodes in the AVL actually represent numbers.)
Lets say we have the numbers (as nodes) 1 5 12 20 23 21 in the AVL tree, the function should return the minimum gap between any two numbers. In this situation it should return "1" which is |20-21| or |21-20|.
It should be done in O(1).
Tried to think alot about it, and I know there is a trick but just couldn't find it, I have spent hours on this.
There was another task which is to find the maximum gap, which is easy, it is the difference between the minimal and maximal number.