Tree Traversal

A common way i've seen of storing transforms is giving each node a pointer to it's parent, and a list of children. For example:

struct Transform {
    Transform parent;
    Transform children[];

    Vector position;
    Quaternion rotation;
    Vector scale;
}

It's easy to do bredth first traversal with this layout, you can either do it recursivley or by utilizing a stack. Both require some allocation for traversal, and the children array requires an allocation as well. We could use a different data structure, a "First Child, Next Sibling" tree which allows for efficient depth first traversal without any additional memory or allocation. Let's explore how.

Instead of storing a parent reference and a list of children, we will store a parent, first child, and next sibling reference.

struct Transform {
    Transform parent;
    Transform firstChild;
    Transform nextSibling;

    Vector position;
    Quaternion rotation;
    Vector scale;
}

With this representation, traversal becomes:

void DepthFirstTraversal(Node root, NodeVisitorFnPtr callback) {
    Node itr = root;
    bool traversing = true;
    while (traversing) {
        callback(itr);

        if (itr->children) {
            itr = itr->firstChild;
        }
        else {
            while (itr->nextSibling == null) {
                if (itr == root) {
                    traversing = false;
                    break;
                }
                itr = itr->parent;
            }
            if (itr == root) { // Prevent stepping to the roots sibling
                traversing = false;
                break;
            }
            itr = itr->nextSibling;
        }
    }
}

Or, you can structure the code to be an interative function:

class Scene {
    Node root

    // Pass NULL to start from root. 
    // Or pass the result of the last call to DepthFirst
    // Returns the next node, or NULL on exit
    Node DepthFirst(Node iter = null) {
        if (iter == null) {
            return root;
        }

        if (iter->firstChild) {
            iter = iter->firstChild;
        }
        else {
            while (iter->nextSibling == null) {
                if (iter == root) {
                    return null;
                }
                iter = iter->parent;
            }
            if (iter == root) {
                return null;
            }
            iter = iter->nextSibling;
        }

        return iter;
    }
}

Now traversal becomes:

for (Node* iter = scene.DepthFirst(); iter != null; iter = scene.DepthFirst(iter)) {
    // Do something
}