Tree Traversal without recursion and without stack and without changing the Tree

Question

This question is from the book Introduction to Algorithms 3rd:

**Each node in the binary tree has 4 properties: key,left,right,parent

EDIT: The binary tree is stored as linked nodes that each one of them has the 4 properties I mentioned.

Write an O(n) time nonrecursive procedure that, given an n-node binary tree, prints out the key of each node. Use no more than constant extra space outside of the tree itself and do not modify the tree, even temporarily, during the procedure.

I tried to find a solution but got nothing...(Also I searched google for solutions for this book, but this question wasn't included there maybe because it was added in later versions).

Answer 1

Here's a solution:

• Let current store the currently visited node (initialized to the root of the tree)
• Let origin represent how we got to the current node. It's one of FROM_PARENT, FROM_LEFT_CHILD, FROM_RIGHT_CHILD. (Initialized to FROM_PARENT)

Algorithm:

• If we came from the top, we print the key and go down left
• If we came back from left, go down right
• If we came back form right, go up.

 

origin = FROM_PARENT;
current = root;

while (current != null) {

    switch (origin) {

    case FROM_PARENT:
        System.out.println(current.key);
        if (current.left != null)
            goLeft();
        else
            origin = FROM_LEFT_CHILD;
        break;

    case FROM_LEFT_CHILD:
        if (current.right != null)
            goRight();
        else
            origin = FROM_RIGHT_CHILD;
        break;

    case FROM_RIGHT_CHILD:
        goToParent();
        break;
    }            
}

Where

static void goToParent() {
    if (current.parent == null) {
        current = null;
        return;
    }
    origin = current == current.parent.left ? FROM_LEFT_CHILD
                                            : FROM_RIGHT_CHILD;
    current = current.parent;
}

static void goLeft() {
    origin = FROM_PARENT;
    current = current.left;
}

static void goRight() {
    origin = FROM_PARENT;
    current = current.right;
}