Like insertAtAbovePrefix but also asserts that key is currently not stored under curr.
See Implementation
Like insertAtAbovePrefix but also asserts that key is currently not stored under curr.