modified depth first traversal of tree

Question

I got this question in an interview with amazon. I was asked to perform a depth first traversal of a tree, without using recursion or stack. I could use a parent pointer for each node, as a part of the structure, but nothing else other than that.(for ex, a "visited" variable" or anything). Please suggest me an algorithm.

Answer 1

For a 'hacky' solution you can use the fact that pointers are usually 4 byte aligned (i.e, last two bits are 0) and use those two bits as your visited flag.

Answer 2

If you have a parent pointer, then you can unwind up the tree without a stack. The only other problem during unwind is "do I need to visit the other child(ren)?" This can be answered simply by comparing pointer values to work out if you've just returned from the left child or the right child (or generalise to N children).

EDIT

Pseudocode (untested):

p_last          = NULL;
p               = p_head;
descend         = true;

while (NULL != p)
{
    p_tmp = p;

    if (descend)
    {
        // ... Node processing here...

        if (0 == p->num_children)
        {
            // No children, so unwind
            p = p_parent;
            descend = false;
        }
        else
        {
            // Visit first child
            p = p->child[0];
        }
    }
    else
    {
        // Find the child we just visited
        for (i = 0; i < p->num_children; i++)
        {
            if (p_last == p->child[i])
            {
                break;
            }
        }
        if (i == num_children-1)
        {
            // Processed last child, so unwind
            p = p_parent;
        }
        else
        {
            // Visit next child
            p = p->p_child[i+1];
            descend = true;
        }
    }

    p_last = p_tmp;
}

Answer 3

The parent pointer is actually all you need. The trick is to consume the tree as you traverse it.

Ugly pseudocode:

cur = treeroot;
while (1) { // Get to bottom of tree
    if (cur.hasLeft) {
        cur = left;
    } else if (cur.hasRight) {
        cur = right;
    } else {
        break;
}

// cur is now the bottom node

while (1) {
    doStuff(cur); // output cur, perform op on it, whatever
    if (!cur.hasParent) { // Done with traversal
        break;
    }
    prev = cur; // So we can tell which way we came up to the parent.
    cur = cur.parent;
    if (cur.hasLeft && cur.left == prev) { // Delete left child; it's done
       cur.hasLeft = false;
    } else if (cur.hasRight && cur.right == prev) { // Delete right child; it's done
       // Note: "else" not desirable if a node should not be able to have the same child in two spots
       cur.hasRight = false;
    }
    if (cur.hasLeft) { // Go all the way to the bottom of the left child
        cur = cur.left;
        while (1) {
            if (cur.hasLeft) {
                cur = cur.left;
            } else if (cur.hasRight) {
                cur = cur.right;
            } else {
                break;
            }
        }
    } else if (cur.hasRight) { // Go all the way to the bottom of the right child
        cur = cur.right;
        while (1) {
            if (cur.hasLeft) {
                cur = cur.left;
            } else if (cur.hasRight) {
                cur = cur.right;
            } else {
                break;
            }
        }
    }
}

Answer 4

Here is my proposition for a binary tree. The language is C#. It's a private method of a binarTree class that holds ints

private Node DFS(int value)
{
    Node current = this.root;
    if(current.data == value) return current;

    while(true)
    {
        //go down-left as far as possible
        while(current.leftChild != null)
        {
            current = current.leftChild;
            if(current.data == value) return current;
        }
        //leftChild is null, but maybe I can go right from here
        while(current.leftChild == null && current.rightChild != null)
        {
            current = current.rightChild;
            if(current.data == value) return current;
        }
        if(current.leftChild == null && current.rightChild == null)
        {
            // Ok, I got to a leaf. Now I have to get back to the last "crossroads"
            // I went down-left from, but there was also down-right option
            while(current.parent != null &&
                  (current == current.parent.rightChild ||
                   current.parent.rightChild == null))
            {
                current = current.parent;
            }
            if(current.parent == null) return null;

            // Ok If I'm here, that means I found the crossroads mentioned before
            // I'll go down-right once and then I should try down-left again
            current = current.parent.rightChild;
            if(current.data == value) return current;
        }
    }
}

If it's not a binary tree, then things get more complicated of course, but the logic is similar. Go down to the leaf taking the first possible child at each level. Once you reach a leaf you go up. Every time you look up at a parent you check if the child you are supposed to come from was the last in parent's list. If not, you take next child and go down again. If yes, you go up and check the following parent. If you get back to the root you searched the whole tree.

EDIT

Ok search and traversals are distinct things, my bad. Here is some modified code for traversals

preorder:

public void preorderTraversal()
{
    Node current = this.root;
    Console.WriteLine(" item: {0} ", current.data);
    while(true)
    {
        while(current.leftChild != null)
        {
            current = current.leftChild;
            Console.WriteLine(" item: {0} ", current.data);
        }
        while(current.leftChild == null && current.rightChild != null)
        {
            current = current.rightChild;
            Console.WriteLine(" item: {0} ", current.data);
        }
        if(current.leftChild == null && current.rightChild == null)
        {
            while(current.parent != null &&
                  (current == current.parent.rightChild ||
                   current.parent.rightChild == null))
            {
                current = current.parent;
            }
            if(current.parent == null)
            {
                return;
            }
            else
            {
                current = current.parent.rightChild;
                Console.WriteLine(" item: {0} ", current.data);
            }
        }
    }
}

inorder:

public void inorderTraversal()
{
    Node current = this.root;
    while(true)
    {
        while(current.leftChild != null)
        {
            current = current.leftChild;
        }
        Console.WriteLine(" item: {0} ", current.data);
        while(current.leftChild == null && current.rightChild != null)
        {
            current = current.rightChild;
            Console.WriteLine(" item: {0} ", current.data);
        }
        if(current.leftChild == null && current.rightChild == null)
        {
            while(current.parent != null &&
                  (current == current.parent.rightChild ||
                   current.parent.rightChild == null))
            {
                    current = current.parent;
                    if(current.rightChild == null)
                    {
                        Console.WriteLine(" item: {0} ", current.data);
                    }
            }
            if(current.parent == null)
            {
                return;
            }
            else
            {
                Console.WriteLine(" item: {0} ", current.parent.data);
                current = current.parent.rightChild;
            }
        }
    }
}

postorder:

public void postorderTraversal()
{
    Node current = this.root;
    while(true)
    {
        while(true)
        {
            if(current.leftChild != null)
            {
                current = current.leftChild;
            }
            else if(current.rightChild != null)
            {
                current = current.rightChild;
            }
            else
            {
                break;
            }
        }
        while(current.parent != null &&
              (current == current.parent.rightChild ||
               current.parent.rightChild == null))
        {
            Console.WriteLine(" item: {0} ", current.data);
            current = current.parent;
        }
        Console.WriteLine(" item: {0} ", current.data);
        if(current.parent == null)
        {
            return;
        }
        else
        {
            current = current.parent.rightChild;
        }
    }
}

Answer 5

This shows how I'd do it in C. It demonstrates both pre-order and post-order traversal, and is generalised for 0..N children of each node.

struct node {
    struct node *parent;
    struct node *child[NCHILD];
};

void dfs(struct node *head, void (*visit_preorder)(struct node *n), void (*visit_postorder)(struct node *n))
{
    struct node *current = head;
    struct node *prev = head;

    while (current)
    {
        int i;

        /* preorder traversal */
        if (prev == current->parent)
            visit_preorder(current);

        /* Find first child to visit */
        for (i = NCHILD; i > 0; i--)
        {
            if (prev == current->child[i - 1])
                break;
        }
        while (i < NCHILD && current->child[i] == NULL)
            i++;

        prev = current;

        if (i < NCHILD)
        {
            /* Descend to current->child[i] */
            current = current->child[i];
        }
        else
        {
            /* Postorder traversal */
            visit_postorder(current);

            /* Ascend back to parent */
            current = current->parent;
        }
    }
}