Rooted tree with huge depth - DFS Traversal algorithm performance

Question

Today, I learnt 3 DFS(Depth First Search) traversals for rooted trees i.e., In-order, Pre-order & Post-order traversals.

For instance, If I consider Pre-order traversal,

typedef struct SiblingTreeNode {
    struct SiblingTreeNode *parent;
    void *item;
    struct SiblingTreeNode *firstChild;
    struct SiblingTreeNode *nextSibling;
} Node;

typedef struct LCRSTree {
    Node *root;
    int size;
} Tree;


void preOrderTraverse(Node * node) {
    visit(node);

    if (node->firstChild) {
        printf("\n|");
        preOrderTraverse(node->firstChild);
    }

    if (node->nextSibling) {
        printf("-->");
        preOrderTraverse(node->nextSibling);
    }
}

void preOrder(Tree *tree) {
    preOrderTraverse(tree->root);
}

---

then nodes are visited in below sequence,

Practically working for NMS(Network management System) applications, We use rooted trees(LCRS representation) to maintain hierarchy of network elements(metrics), where depth of leaf node is pretty huge.

Asymptotically, space complexity of pre-order traversal is O(d), where d is the depth of the lowest leaf.

On applying any of these 3 traversals, there is a great chance for an application to crash, due to stack over flow.

For example - If you consider visiting node sequence(above) call stack is maintained from root to leaf, when you visited 3rd node.

With the given Tree representation above, Without maintaining explicit data structures(like stack), How to optimize the traversal algorithm, on rooted trees?

Note: On construction, Tree looks like this

Answer 1

There is a non-recursive solution for Pre-order traversal, that uses the stack data structure insdead of the call stack in recursive. if memory is still an issue, you can design a stack to offload some of it to storage, and reload it when needed.

void iterativePreorder() {
    TreeNode top;
    if (root == null)
        return;

    Stack<SiblingTreeNode> st = new Stack<SiblingTreeNode>();
    st.push(root);

    while (!st.empty()) {
        top = st.pop();
        //do traversal effect
        if (top.right != null)
            st.push(top.right);
        if (top.left != null)
            st.push(top.left);
    }
}