The fix was very simple, I went to the /usr/local/bin /usr/local/bin and removed everything related to ROS and Catkin. That resolved my issue. The next time when I installed ros-melodic ros-melodic and did rosdep init, init, I saw the rosdep rosdep files in usr/bin/ usr/bin/ and everything worked smooth from there.