Non-recursive chop and clone for Binary Search Tree - Solutions

Hello:

I had a professor in college who enjoyed challenging us. Before I
graduated, he challenge me to print out a Binary Search tree in by-
level order - that way you see nodes ordered by what level/height they
were at.

At the time, I wasn't in the mood; however, I was recently REQUIRED to
figure it out. The problem: I had an unbalanced tree that needed
destroyed. You can usually get away with a recursive (naive/trivial)
implementation, but you're leaving yourself open for a stack overflow
at some point down the line.

So, how do you chop a tree without using recursion? This is a C#
implementation of the solution:

private void chop(NodeBase node)
{
Queue<NodeBase> topDown = new Queue<NodeBase>();
topDown.Enqueue(node);
Stack<NodeBase> bottomUp = new Stack<NodeBase>();
while (!topDown.IsEmpty)
{
NodeBase current = topDown.Head;
topDown.Dequeue();
bottomUp.Push(current);
if (current.Left != null)
{
topDown.Enqueue(current.Left);
}
if (current.Right != null)
{
topDown.Enqueue(current.Right);
}
}
while (!bottomUp.IsEmpty)
{
NodeBase current = bottomUp.Top;
bottomUp.Pop();
current.TransferParent(null);
current.Dispose();
}
}

You essentially do a by-level in reverse. You go the whole way down,
then you go the whole way up, deleting the leafs first! If you didn't
delete the leafs first and an error occurred while deleting, you could
accidentally leave a partial structure in memory, with no way of
retrieving it later (not good for non-memory managed languages). It
also makes sense to maintain the tree invariant even when deleting,
simply for taste. It is easy to modify the snippet above to delete on
the way down.

Cloning is essentially the same, except care has to be made to ensure
that children point to parents and vice-versa. Also, you always need
to have the context of what you are copying, so you must maintain a
queue of the source nodes and the to-be-copied nodes.

private AVLTree<T> clone()
{
AVLTree<T> copy = new AVLTree<T>(predicate);
if (size > 0)
{
Queue<Node> nodes = new Queue<Node>();
Queue<Node> originals = new Queue<Node>();
Node root = new Node(copy.dummy, null, null,
((Node)dummy.Parent).Value);
nodes.Enqueue(root);
originals.Enqueue((Node)dummy.Parent);
while (!originals.IsEmpty)
{
Node parent = nodes.Head;
Node source = originals.Head;
if (source.Left != null)
{
Node node = new Node(parent, null, null,
((Node)source.Left).Value);
parent.Left = node;
nodes.Enqueue(node);
originals.Enqueue((Node)source.Left);
}
if (source.Right != null)
{
Node node = new Node(parent, null, null,
((Node)source.Right).Value);
parent.Right = node;
nodes.Enqueue(node);
originals.Enqueue((Node)source.Right);
}
nodes.Dequeue();
originals.Dequeue();
}
copy.dummy.Parent = root;
copy.dummy.Left = root.LeftMost();
copy.dummy.Right = root.RightMost();
copy.size = size;
}
return copy;
}

While both these solutions require containers of pointers to Nodes,
the memory usage is almost equivalent (slightly less in general) to
recursion. These solutions are also generally memory-leak safe-r and
escape the stack overflowing.

Sorry that the examples are so concrete (I copied them from my data
structure library). I just thought I would share them since they
aren't as trivial as the ones we are made to implement in school.
.

Quantcast