Recursive tail traverse without cycles

Question

I want to scroll the next tail of the tree structure recursively , without departing from the loops :

const o = {x:0,c:[{x:1,c:[{x:2,c:[{x:3},{x:4,c:[{x:5}]},{x:6}]},{x:7},{x:8}]},{x:9}]}; 0 / \ 1 9 / | \ 2 7 8 / | \ 3 4 6 | 5 

Desired result: /0/1/2/3/4/5/6/7/8/9 0/1/2/3/4/5/6/7/8/9

I assume that closing is required to resolve tail recursion. I have tried this so far:

 const traverse = o => { const nextDepth = (o, index, acc) => { const nextBreadth = () => o["c"] && o["c"][index + 1] ? nextDepth(o["c"][index + 1], index + 1, acc) : acc; acc = o["c"] ? nextDepth(o["c"][0], index, acc + "/" + o["x"]) // not in tail pos : acc + "/" + o["x"]; return nextBreadth(); }; return nextDepth(o, 0, ""); }; traverse(o); // /0/1/2/3/4/5/7/9 

Siblings do not intersect properly. How can I do that?

Answer 1

As @Bergi wrote, if you manually support the stack, it's simple.

 const o = {x:0,c:[{x:1,c:[{x:2,c:[{x:3},{x:4,c:[{x:5}]},{x:6}]},{x:7},{x:8}]},{x:9}]} const traverse = g => { const dfs = (stack, head) => (head.c || []).concat(stack) const loop = (acc, stack) => { if (stack.length === 0) { return acc } const [head, ...tail] = stack return loop(`${acc}/${head.x}`, dfs(tail, head)) } return loop('', [g]) } console.log(traverse(o)) console.log(traverse(o) === '/0/1/2/3/4/5/6/7/8/9')