Functions to convert between depth first and breadth first traversals of a complete tree

Question

Problem: Consider a complete k-ary tree with l levels, with nodes labelled by their rank in a breadth first traversal. Compute the list of labels in the order that they are traversed in the depth first traversal.

For example, for a binary tree with 3 levels, the required list is: [0 1 3 7 8 4 9 10 2 5 11 12 6 13 14]

One way to do this is to actually construct a tree structure and traverse it twice; The first traversal is breadth first, labelling the nodes 0,1,2,.. as you go. The second traversal is depth first, reporting the labels 0,1,3,7,.. as you go.

I'm interested in a method that avoids constructing a tree in memory. I realize that the size of such a tree is comparable to the size of the output, but I'm hoping that the solution will allow for a "streaming" output (ie one that needs not be stored entirely in memory).

I am also interested in the companion problem; start with a tree labelled according to a depth first traversal and generate the labels of a breadth first traversal. I imagine that the solution to this problem will be, in some sense, dual to the first problem.

Answer 1

You don't actually need to construct the tree. You can do the depth first traversal using just the BFS labels instead of pointers to actual nodes.

Using BFS position labels to represent the nodes in k-ary tree:

• The root is 0
• The first child of any node n is k*n + 1
• The right sibling of a node n, if it has one, is n+1

in code it looks like this:

class Whatever
{
    static void addSubtree(List<Integer> list, int node, int k, int levelsleft)
    {
        if (levelsleft < 1)
        {
            return;
        }
        list.add(node);
        for (int i=0; i<k; i++)
        {
            addSubtree(list, node*k+i+1, k, levelsleft-1);
        }
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        int K = 2, LEVELS = 4;
        ArrayList<Integer> list = new ArrayList<>();
        addSubtree(list, 0, K, LEVELS);
        System.out.println(list);
    }
}

This is actually used all the time to represent a binary heap in an array -- the nodes are the array elements in BFS order, and the tree is traversed by performing these operations on indexes.