If this blog helped you in any way (professionally), please donate a dollar here

Tuesday, August 9, 2011

Iterative Inorder Traversal of Binary Search Tree

A student from my undergrad college asked an innocent question to me on a facebook group to write an iterative implementation for In-Order Traversal of a Binary Search Tree. Of course I obliged and wrote up a code. However, I had never dug deeper into the properties of such traversals before and my observation was quite unexpected.

I was asked a question in the M.Tech. programme interview at NIT Durgapur about the significance of In-Order traversals of BSTs. I wasn't aware of any! So I gave a prompt reply, that it prints the elements in a sorted order. I was sure I was correct but the expression on their faces led me believing I was surely wrong! Oh well, I never did study theory before, so I guess my anguish was justified.

So, for my fellow junior, here's the code I promised: