This series of Google documents contains my short notes and descriptions to various algorithmic problems. It closely follows the contents in Introduction to Algorithms, 3rd Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein – The MIT Press (a.k.a CLRS). These are publicly made available for sharing with rest of the community.
My intention is to share what my understanding of this subject (from a serious one term study at University of Waterloo) and learn from you – a single term course cannot cover all the topics in this book. So we need to learn ourselves – and that is adventurous, wouldn’t you agree on that? I am sure you would.
You may use this as a cheat sheet to help you refresh your memory, say in preparation for an algorithm interview.
All credits should go to the authors of the book. There is no substitute for the breath and depth of coverage on these beautiful problems as given in this book. If you are student or a professional – then, in my opinion you must own one.
Google, The MIT Press and University of Waterloo are registered trademarks and are used here for reference purposes only. If you think I am violating anyone’s rights – give me a shout!
Above Disclaimer and Acknowledgement notice was last updated on Feb 11th, 20121. The business of sorting – A walk through linear time sorting algorithms
Sorting is one of the primary area of study in Computer Science. How to sort, ladies and gentlemen, the question to ask? The Business of Sorting
2. It’s a monkey business – Tree traversal
The nice thing about a recursive solution is that it implicitly uses a (function / method) stack to enforce the in-order traversal. So, what do you think could be a potential problem with this solution – well in the worst case scenario of a binary tree its depth could be bound from above by O(n). So if n is large then our solution above will soon eat up all the spaces in the stack (memory). Therefore an iterative solution is preferable. There is an algorithm commonly known as Morris Tree Traversal algorithm – the issue with this algorithm is that it modifies the tree temporarily – though it is reverted back to original state at the end.
Following is my algorithm for traversing a tree without modifying it – even temporarily and using constant additional space.
Neural Dump 
Well, if you don’t have a parent pointer, how can you realize the constant memory traversal?
Thanks for the reply James. On line 9 of IN-ORDER(T) routine, I have commented as follows
// π denotes the parent, a convention inherited from CLRS — (Book, MIT press). Hope that helps.
I know. I mean it can only work if given the parent pointer, sometimes the interviewer will not provide this pointer, in this way, maybe you can only use Morris.
Also, how do you realize preOrder and postOrder using constant space?
If there is no child to parent reference then rules of games have changed and above solution does not apply.
As you must be able to note, this algorithm does NOT use memory in anyway proportional to the size of the input – it uses constant number of references and knowledge of structural properties inherent to this data structure (and assumptions such as reference to a parent from a child node) to traverse it.