Iterative Inorder Traversal B-Tree

My end goal is to do a findKthElement function and the only way I can think of is to perform iterative inorder traversal so that I can keep a counter, which obviously doesn’t work if its recursive. I have tried my best at an implementation similar to a BST but its not working, just printing the same thing infinately. Here is my attempt:

public void findKth() {
        Stack<BTreeNode> s = new Stack<>();
        BTreeNode current = this.root;
        while(current != null || !s.isEmpty()) {
            int i;
            for(i = 0; i < current.numNodes; i++) {
                if(!current.isLeaf) {
                    s.push(current);
                    current = current.children[i];
                }
            }
            current = s.pop();
            for(int j = 0; j < current.numNodes; j++) {
                System.out.println(current.keys[j].getName());
            }
        }
    }

Answer

keep a counter, which obviously doesn’t work if its recursive

There is no problem keeping a counter in a recursive solution. You just need to make sure it’s a mutable reference. For example:

public class Counter {
    private int count;
    public boolean complete() { return count == 0; }
    public void decrement() { count--; }
}

Optional<Node> findKthChild(Node node, Counter counter) {
    if (counter.isLeaf()) {
        if (counter.complete())
            return Optional.of(node);
        counter.decrement();
    } else {
        for (Node child: getChildren()) {
            Optional<Node> kthChild = findKthChild(child, counter);
            if (kthChild.isPresent())
                return kthChild;
        }
    }
    return Optional.empty();
}

If you’re familiar with streams the internal for loop could be:

return getChildren().stream()
    .map(ch -> findKthChild(ch, counter))
    .filter(Optional::isPresent)
    .findFirst().orElse(Optional.empty());