How to root Kindle Fire HD 8.9"
My Kindle OS is 8.5.1 where the above solutions don't work (nor any other I found via google).

However, I found a thread on xda developers which pointed to a file name root_master.apk and this one successfully rooted my device.

When using this apk, the process was partially in chinese (which I don't understand), but it worked. Not sure if this app is safe though, so use at your own risk.