How to traverse this tree in reverse order

Question

I found an implementation of the Morris tree traversal,

It works fine,,, but having a bit of a problem trying to traverse the tree in reverse order.. -

    void MorrisTraversal(struct Node *root)
    {  
    struct Node *p,*pre;
    if(root==0) { return; }
    for(p=root;p!=0;)
    {
    if(p->Left==0) { printf(" %d ",p->Data); p=p->Right; continue; }
    for(pre=p->Left;pre->Right!=0 && pre->Right!=p;pre=pre->Right) { }
    if(pre->Right==0)
        { pre->Right=p; p=p->Left; continue; }
    else
        { pre->Right=0; printf(" %d ",p->Data); p=p->Right; continue; }

    }
}

Solution 1

By reverse order, I'm assuming you mean reverse inorder traversal. You have at least two options:

1. You could modify the code and swap all the ->Right pointer references with ->Left ones.

2. You could replace the two printf statements with pushes onto a stack. Once the algorithm completes, you would then pop off the data from the stack to print them. This however defeats the whole purpose of the Morris traversal algorithm, which was to be stackless.

This related SO thread might help you understanding.

I hope this helps.

Solution 2

Here is one sample in Java. Click Here for one more sample using iteration instead of recursion.

public int depthOfTree(TreeNode node){
    if(node == null){
        return 0;
    }

    int leftDepth = depthOfTree(node.left);
    int rightDepth = depthOfTree(node.right);

    if(leftDepth > rightDepth){
        return leftDepth+1;
    } else {
        return rightDepth+1;
    }
}

//Reverse Level with recursion
public void reverseLevelOrder(TreeNode node){
    int depth = depthOfTree(node);

    for(int i=depth;i>0;i--){
        printTree(node,i);
    }
}

public void printTree(TreeNode node, int level){
    if(node == null){
        return;
    }
    if(level == 1){
        System.out.print(node.data+" ,");
    } else if(level>1){
        printTree(node.left, level-1);
        printTree(node.right, level-1);
    }
}