Clever Geek Handbook

Traversing a tree without recursion and without a stack and without changing the tree

This question is from the book Introduction to 3rd party algorithms:

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

EDIT: The binary tree is stored as linked nodes, each with 4 properties that I mentioned.

Write a non-recursive O (n) time routine that, given an n-node binary tree, outputs the key from each node. Use no more than permanent extra space outside the tree itself and do not alter 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 was not included there, perhaps because it was added in later versions).

+3


source to share


1 answer


Here's the solution:

  • Let's current

    store the currently visited node (initialized by the tree root)
  • Let's origin

    represent how we got to the current node. This is one of FROM_PARENT

    , FROM_LEFT_CHILD

    , FROM_RIGHT_CHILD

    . (Initialized before FROM_PARENT

    )

Algorithm:

  • If we come from above, we type the key and go left
  • If we come back from the left side, go down to the right
  • If we get back right, come 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;
}
+4


source






More articles:


All Articles