TreeMap internally uses Red-Black tree as internal DS. Tree is having Time complexity of O(log n). So, It also should have the same time complexity. TreeMap does not allow null key but null values are allowed.