Preorder traversal of a quadtree

Question

So I know for a binary tree the general way to preorder traverse it is like this

void displayPreOrder(TreeNode node)
{
    if(node != null)
    {
        displayPreorder(node.left);
        displayPreorder(node.right);
        System.out.println(node.value);
    }
}

But I'm having trouble trying to wrap my head around a preorder traversal of a quadtree. I've tried to find some resources, but left empty handed. Any hint?

Answer 1

The code you posted is for a postorder traversal of a binary tree. For a quadtree, you just need to visit all children instead of just left and right.

For simplicity, I'll assume that TreeNode defines a method children() that returns an iterator or a List of the node's children in some well-defined order. If that's not available, just iterate through the children using whatever mechanism is available.

void displayPreOrder(TreeNode node)
{
    if(node != null)
    {
        // visit the root first for pre-order
        System.out.println(node.value);
        for (TreeNode child : node.children()) {
            displayPreorder(child)
        }
    }
}

(P.S. This works for binary trees as well, given the right iteration mechanism.)