You need to be very careful about how you partition the keys between the subtrees rooted at the children of the root.