print_depth.py

def depth(dictionary, count=0):
	count +=1

	# I use sorted for our case
	# to print out as it's expected in the written task
	# We should use OrderDict as input if it's required to keep the order of dict.
	for key, value in sorted(dictionary.items()):
		print key, count
	
	if isinstance(value, dict):
		depth(value, count)
		
if __name__ == "__main__":
	a = {"key1":1,
		 "key2": {
		 	"key3": 1,
		 	"key4": {
		 		"key5":1,
		 	}
	    }
	}
	
	depth(a)