How to traverse BTree in-order without recursion in iterative style?

Question

I need B-Tree LNR traversal (in-order). I've found an algorithm for B-Tree traversal here. How I can implement it without recursion in iterative way? I've found this question but there is no answer and the code in the question is so unclear and seems incorrect. At least, this is not the LNR and it's not suitable for me. Also I've found a lot of example of simple binary tree traversal but I need exactly B-Tree.

I use Rust but I'll be happy to see answer in any language or pseudocode.

Answer 1

As already mentioned in comments: if you do not want to use recursion -- which would be the way to go -- then you'll have to mimic it using a stack.

An entry on that stack would be a pair consisting of:

• a reference to a node, and
• a current index (0...m-1) within that node, where m is the number of branches at that node

As an example, I'll use the following B-tree:

...and use a JSON representation of it:

{
    "keys": [29],
    "children": [{
        "keys": [15, 21],
        "children": [{
            "keys": [11, 12]
        }, {
            "keys": [18, 20]
        }, {
            "keys": [23, 25, 27]
        }]
    }, {
        "keys": [35, 42],
        "children": [{
            "keys": [31, 33]
        }, {
            "keys": [36, 39]
        }, {
            "keys": [45, 47, 50, 55]
        }]
    }]
}

Here is an implementation of an iterate function in JavaScript, which returns an iterator over the keys in LNR order:

function * iterate(node) {
    let stack = []; // stack of [node, child-index] pairs
    
    stack.push([node, 0]);
    while (stack.length > 0) {
        let [node, i] = stack.pop();
        if (!("children" in node)) { // bottom level has no "children" member
            for (let key of node.keys) {
                yield key;
            }
        } else if (i < node.children.length) {
            if (i > 0) {
                yield node.keys[i-1];
            }
            stack.push([node, i+1]);
            stack.push([node.children[i], 0]);
        }
    }
}

// The example B-tree:
const btree = {"keys": [29],"children": [{"keys": [15, 21],"children": [{"keys": [11, 12]}, {"keys": [18, 20]}, {"keys": [23, 25, 27]}]}, {"keys": [35, 42],"children": [{"keys": [31, 33]}, {"keys": [36, 39]}, {"keys": [45, 47, 50, 55]}]}]};

// Consume the iterator and output
console.log(...iterate(btree));