tdrunner95 - 6 months ago 63

Java 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

The code you posted is for a **post**order 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.)