Suggest an editImprove this articleRefine the answer for “What does the stack do during traversal without recursion?”. Your changes go to moderation before they’re published.Approval requiredContentWhat you’re changing🇺🇸EN🇺🇦UAPreviewTitle (EN)Short answer (EN)**The stack in a non-recursive traversal** replaces the system call stack: it holds state frames (a node and the context of processing it), provides LIFO returns to "return points," and lets you emulate pre/in/post processing of nodes and manage backtracking. This makes a depth-first traversal possible without recursion, with precise control over visit order. **Key point:** a stack (LIFO) gives a depth-first traversal and natural backtracking, an analog of recursion; a queue (FIFO) is needed for breadth-first traversal (BFS).Shown above the full answer for quick recall.Answer (EN)Image## Short answer The stack in a non-recursive traversal replaces the system call stack: it holds state frames (a node and the context of processing it), provides LIFO returns to "return points," and lets you emulate pre/in/post processing of nodes and manage backtracking. This makes a depth-first traversal possible without recursion, with precise control over visit order. ## Details ### What the stack does in a non-recursive traversal - Emulates the call stack: each push is an "entry" into a subtask, each pop is a "return." - Holds return points and context: where we were, what's already processed, what's left (the processing phase, child index, iterator, and so on). - Provides LIFO order for backtracking: the last branch goes deeper than the first, which is exactly what a depth-first traversal (DFS) is. - Lets you implement different traversal orders (preorder/inorder/postorder) by controlling when a node is processed and the order in which neighbors/children are pushed. - Gives explicit control over memory and traversal order, avoiding the system stack's depth limit. ### How it works step by step 1. Push the starting node (or state frame) onto the stack. 2. While the stack isn't empty: pop the top. 3. Process the node in the right phase (before/between/after children), depending on the traversal variant. 4. Push neighbors/children onto the stack in the order that makes the next pop yield the desired visit order (usually pushed in reverse display order). ### What exactly goes onto the stack - A reference to the node (a vertex of the tree/graph). - The processing phase/state: enter/pre, mid/in, exit/post (often a boolean visited/expanded flag). - The current child's index, or a neighbor iterator (if children need to be processed one at a time). - Arbitrary context: a reference to the parent, an accumulated path/depth, intermediate computations. ### Why a stack, not a queue A stack (LIFO) gives a depth-first traversal and natural backtracking, an analog of recursion. A queue (FIFO) is needed for a breadth-first traversal (BFS), where it matters that all vertices of the current level are processed first. ### Traversal orders and the stack's role - Preorder (node-left-right): we process the node right after popping it; then push the right child, then the left. - Inorder (left-node-right): the stack holds the path to the leftmost node; after popping we process the node and go into the right subtree. - Postorder (left-right-node): we use a flag/phase or two stacks; a node is processed only after its children. ## Code examples (JavaScript) ### 1) DFS on a tree: preorder (node-left-right) ``` function preorderIter(root) { if (!root) return []; const res = []; const stack = [root]; while (stack.length) { const node = stack.pop(); res.push(node.val); // pre-processing if (node.right) stack.push(node.right); // push right first if (node.left) stack.push(node.left); // so left comes off the stack sooner } return res; } // Node shape: // { val: number, left: Node|null, right: Node|null } ``` ### 2) DFS on a tree: inorder (left-node-right) ``` function inorderIter(root) { const res = []; const stack = []; let curr = root; while (curr || stack.length) { while (curr) { // go down the left branches, remembering the path stack.push(curr); curr = curr.left; } curr = stack.pop(); // the left subtree is exhausted, process the node res.push(curr.val); curr = curr.right; // then go into the right subtree } return res; } ``` ### 3) DFS on a tree: postorder (left-right-node) via a state flag ``` function postorderIter(root) { const res = []; if (!root) return res; const stack = [{ node: root, visited: false }]; while (stack.length) { const { node, visited } = stack.pop(); if (!node) continue; if (visited) { res.push(node.val); // post-processing } else { // Push a marker to revisit after the children stack.push({ node, visited: true }); if (node.right) stack.push({ node: node.right, visited: false }); if (node.left) stack.push({ node: node.left, visited: false }); } } return res; } ``` ### 4) DFS on a graph (iterative, with a stack) ``` function dfsGraph(adj, start) { // adj: Map<Vertex, Vertex[]> or an object { v: [u1, u2, ...] } const visited = new Set(); const stack = [start]; const order = []; while (stack.length) { const v = stack.pop(); if (visited.has(v)) continue; // important, to avoid cycles visited.add(v); order.push(v); const neighbors = (adj.get ? adj.get(v) : adj[v]) || []; for (let i = neighbors.length - 1; i >= 0; i--) { const u = neighbors[i]; if (!visited.has(u)) stack.push(u); } } return order; } ``` ## Generic "explicit stack of frames" template ``` function dfsIterGeneric(start) { // A frame holds the node and a phase: 'enter' (before children) or 'exit' (after children) const stack = [{ node: start, state: 'enter' }]; while (stack.length) { const frame = stack.pop(); const { node, state } = frame; if (!node) continue; if (state === 'enter') { // 1) pre-processing // ... // 2) Schedule post-processing stack.push({ node, state: 'exit' }); // 3) Push children in reverse order, so the first logical child goes first const children = node.children || []; for (let i = children.length - 1; i >= 0; i--) { stack.push({ node: children[i], state: 'enter' }); } } else { // post-processing // ... } } } ``` ## Common errors - Missing a visited set for a graph, causing infinite loops. - The wrong push order, breaking the desired traversal order. - Ignoring the phase/visited flag for postorder, so a node gets processed too early. - Needlessly duplicating nodes on the stack, wasting memory and doing extra work. ## Relation to recursion Recursion automatically creates frames on the system stack: local variables, the return position, the phase. In the non-recursive approach, you explicitly create such frames and manage them by hand through your own stack, getting the same effect but with control over order and depth limits.For the reviewerNote to the moderator (optional)Visible only to the moderator. Helps review go faster.