# Transforming an immutable binary tree without recursion [closed]

I'm struggling on this one. I have a Binary Decision Diagram, which is pretty much tree-like. Each node has a hi and lo node. I need to recurse into the tree, and if some conditions are the case replace the node with a new node. Nodes are immutable. So when I encounter something I have to change, I have to return the new version of the node all the way up. Ultimately the root changes. Specifically I'm trying to implement the RESTRICT algorithm for ROBDDs.

And I have! This works fine (C#, sorry?)

        Node Restrict(Node node, Func<Variable, bool?> npoint)
{
if (node == context.Term0 || node == context.Term1)
return node;

// value has been restricted, replace with true or false path
if (npoint(node.Variable) is bool value)
return Restrict(value ? node.Hi : node.Lo, npoint);

var lo = Restrict(node.Lo, npoint);
var hi = Restrict(node.Hi, npoint);
return new Node(node.Variable, lo, hi);
}


However, my diagram is rather huge. And I'm running out of stack space.

So, I'm trying to come up with a way to do this without recursion. I've tried a few things but haven't come up with anything that works. As I start to expand it out, it gets pretty complicated and I start losing track of stuff.

Can somebody point me to some resource on this?

• StackOverflow.com is the site in this network for getting help with specific code. Answers here should really stick to the principles of turning recursive code into iterative code with a stack of continuations. I suggest you press the "flag" link and make a custom flag to request migration. – Peter Taylor Aug 2 '19 at 6:46