Print
In-Order traversal without recursion and stack
InOrder
traversal means Left, Root, Right
Thus
once left subtree is fully exhausted, we print the parent and then
move on to right subtree. But since the left subtree does not have a
parent pointer, then we cannot come back to the parent after subtree
has been traversed.
Also,
note the following:
1)
Parent of left subtree is inorder successor of the left subtree.
2)
We do not need to get back to parent after traversing right subtree.
So
if we somehow determine the inorder successor of a subtree when that
subtree is fully traversed, then we shall be able to traverse the
tree fully.
Normally,
this purpose is solved by a stack.
But
we can also temporarily make the tree a threaded binary tree (while
traversing itself) and avoid the use of a stack.
void MorrisTraversal (Node root)
{
Node curr = root;
while (curr != null)
{
if (curr.left != null)
{
// find inorder predecessor of left subtree
Node pre = curr.left;
while (pre.right != null && pre.right != curr)
{
pre = pre.right;
}
if (pre.right == null)
{
// Threaded property for this node was not set. Set it now
pre.right = curr;
curr = curr.left; // Thread created. Switch to this subtree now
} else
{
// This means pre.right = curr
// Which implies that thread for this was set already,
// So we do not need to traverse this subtree again
pre.right = null; // reset the thread we created earlier
print (curr);
curr = curr.right;
}
} else
{
// no left subtree, print yourself and get to right subtree
print (curr);
// we will never get right=null till the end because of above threads
curr = curr.right;
}
}
}
|
|
Morris
traversal shown above avoids the use of a stack but is also more time
consuming since we need to traverse the tree for creating and
deleting threads.
For
a subtree with ‘N’ nodes, one has to traverse
approximately logN nodes to create/delete the thread.
However,
that time can be thought of as comparable to the creation of new
nodes, push and pop operations in the stack.
|
