Morris Magic

While preparing for tech companies, I have had a lot much insights into the computer science and boy, aint I get bamboozled!! Already I find trees and graphs one of the challenging area, given that I need to think about these problems both from iterative and recursive ways to solve problems just in case interviewer asks me....

Recently I came across a question that asked for NO recursion, NO stack usage to visit the tree INLINE! I was stumped. It was the I tried drawing 2 pages and gave up on algo. It was pretty cool solution at the end as I figured from the solution. Mr Morris came up with the idea of changing the whole tree pointers while traversing one node after the other. Then visit and then change the pointers back as though nothing had happened.

Implementation in Java:

public void inLineMorrisIterative(BTreeNode node) {
if (node == null)
return;

while (node != null) {
// Go to the far left of this node
if (node.left == null) {
// Visit this node
visit(node);
// Go right
node = node.right;
} else {
// There is a left subtree
BTreeNode tmp = node.left;
// Get hold of the right most until it reaches extreme right or
// pick up its child which is also its parent
while (tmp.right != null && tmp.right != node) {
tmp = tmp.right;
}
if (tmp.right == null) {// If rightmost
tmp.right = node; // link it to the node.
node = node.left; // Get the node to the root of the left
// subtree
} else { // We get to the parent of tmp
// Visit the node then
visit(node);
// Break the temporary link
tmp.right = null;
// Move right
node = node.right;
}
}
}
}