level-order, tree traversal - How to keep track of the level?

Question

How to keep track of the level while traversing a binary tree in level order or breadth-first order?

The nodes in the binary tree have left and right references only.

I want to be able to distinguish between each row of nodes.

Here is my method for level-order traversal:

private static Queue<Node> traverseLevelOrder(final Node node)
{
    final Queue<Node> temporaryQueue = new LinkedList<Node>(); // Temporary queue is used for traversal.
    final Queue<Node> permanentQueue = new LinkedList<Node>(); // Permanent queue is used for node storage.

    // Add the root node, as current, to the queue.
    Node current = node;
    temporaryQueue.add(current);
    permanentQueue.add(current);

    while (!temporaryQueue.isEmpty())
    {
        current = temporaryQueue.remove();
        System.out.println(String.valueOf(current));

        // Check current's children.
        if (current != null)
        {
            final Node left = current.getLeft();
            final Node right = current.getRight();

            current = left;
            if (current != null)
            {
                temporaryQueue.add(current);
                permanentQueue.add(current);
            }

            current = right;
            if (current != null)
            {
                temporaryQueue.add(current);
                permanentQueue.add(current);
            }
        }
    }

    return permanentQueue;
}

Answer 1

It is possible to keep track of the level when you know that the number of nodes doubles each level. For example, in level 0, there is only 1 node; in level 1, there are 2 nodes; in level 2, there are 4 nodes; in level 3, there are 8 nodes; in level 4, there are 16 nodes; etc.

The code for grouping each level of nodes into an array using level-order traversal in Java may look like this:

private static Node[][] toArrayLevels(final Node node)
{
    final Queue<Node> temporaryQueue = new LinkedList<Node>(); // Temporary queue is used for level-order traversal.

    final ArrayList<Node[]> tree = new ArrayList<Node[]>(); // Levels containing their nodes.
    ArrayList<Node> nodes = new ArrayList<Node>(); // Current level containing its nodes.

    Node[][] treeArray = new Node[][]{};
    Node[] nodesArray = new Node[]{};

    Node current = node; // Level 0.
    int level = 1; // Node's children are level 1.
    temporaryQueue.add(current);

    nodes.add(current);
    tree.add(nodes.toArray(nodesArray));

    nodes = new ArrayList<Node>(2);

    while (!temporaryQueue.isEmpty())
    {
        // When the nodes completely fill the maximum spaces (2 ^ level) allowed on the current level, start the next level.
        if (nodes.size() >= Math.pow(2, level))
        {
            tree.add(nodes.toArray(nodesArray));
            nodes = new ArrayList<Node>((int) Math.pow(2, level));
            level += 1;
        }

        current = temporaryQueue.remove();

        // Check current's children.
        if (current != null)
        {
            final Node left = current.getLeft();
            final Node right = current.getRight();

            temporaryQueue.add(left);
            nodes.add(left);

            temporaryQueue.add(right);
            nodes.add(right);
        }
        else
        {
            // Null nodes fill spaces used to maintain the structural alignment of the tree.
            nodes.add(null);
            nodes.add(null);
        }
    }

    // Push remaining nodes.
    if (nodes.size() > 0)
    {
        tree.add(nodes.toArray(nodesArray));
    }

    return (tree.toArray(treeArray));
}

It checks the number of nodes on the current level. When the nodes have filled the current level, then it starts a new level.

As an example, a binary tree may look like this:

Level 0:                                60
                         /                              \
Level 1:                50                              65
                 /              \                /              \
Level 2:        49              55              --              66
             /      \        /      \        /      \        /      \
Level 3:    --      --      --      --      --      --      --      71

Here is the output of the example:

System.out.println(Arrays.deepToString(binaryTree.toArrayLevels()));

[[{60}], [{50}, {65}], [{49}, {55}, null, {66}], [null, null, null, null, null, null, null, {71}], [null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null]]

[
    [{60}], // Level 0.
    [{50}, {65}], // Level 1.
    [{49}, {55}, null, {66}], // Level 2.
    [null, null, null, null, null, null, null, {71}], // Level 3.
    [null, null, null, null, null, null, null, null, null, null, null, null, null, null, null, null] // Level 4.
]

Here is the JavaScript version:

function toArrayLevels(node)
{
    var temporary = []; // Temporary is used for level-order traversal.

    var tree = []; // Levels containing their nodes.
    var nodes = []; // Current level containing its nodes.

    var current = node; // Level 0.
    var level = 1; // Node's children are level 1.

    temporary.push(current);
    tree.push([current]);

    while (temporary.length > 0)
    {
        // When the nodes completely fill the maximum spaces (2 ^ level) allowed on the current level, start the next level.
        if (nodes.length >= Math.pow(2, level))
        {
            tree.push(nodes);
            nodes = [];
            level += 1;
        }

        current = temporary.shift();

        // Check current's children.
        if (current !== null)
        {
            var left = current.left;
            var right = current.right;

            temporary.push(left);
            nodes.push(left);

            temporary.push(right);
            nodes.push(right);
        }
        else
        {
            // Null nodes fill spaces used to maintain the structural alignment of the tree.
            nodes.push(null);
            nodes.push(null);
        }
    }

    // Push remaining nodes.
    if (nodes.length > 0)
    {
        tree.push(nodes);
    }

    return tree;
}