non-recursive free of binary tree

**cmoroney** · 10-30-2013

Hello,

I have a very deep binary tree to delete and I'm getting a stack overflow using the usual recursive solution so I'd like to get a handle on how to do a free of a binary tree without blowing up the stack with endless recursive calls.

A snippet of C-code that accomplishes this task would be very much appreciated, as would an explanation of the algorithm.

This is what I've been able to get so far, gleaned from a google search. It's easy to find the deepest point in the tree, but then I'm not sure as to how to back myself up the tree, deleting nodes as I go.

insert

Code:

      node = *Tree;
      while (*Tree) {
    while (node) {
      if (node->left) {
        node = node->left;
      } else if (n->right) {
        node = node->right;
      } else {
        if (node == *Tree) {
          *Tree = 0;
        }
        PGS_MEM_Free(node);
        node = 0;
        break;
      }
    }
      }

Thanks for any help,

Catherine

**anduril462** · 10-30-2013

You wont get free code, it's against our policy and besides, you wont learn very well, and this might be homework -- we wouldn't want to contribute to academic dishonesty.

EDIT: I don't mean to say you are trying to cheat, you actually made some effort and posted code.
EDIT 2: Your code does find the leaves and deletes them, but you have no way to go back up a level, and you don't want to have to dive down from the top again to a leaf, especially when your tree is apparently very deep/tall.

One way is to create your own "stack". You can use dynamic memory to avoid stack limitations. As you traverse down to the leaf node, push tree nodes on your stack (yes, a you will have a stack of tree nodes). That way once you're done deleting a leaf, you just pop back up to the level above. Google "iterative in-order binary tree traversal" or similar for some more info.

Another option is to always delete the root, and adjust the left or right subtree to move a new node into the root position. I *think* this can be done iteratively without using any extra data structures (like a stack) or any extra memory, save for maybe a few temp node pointers, but that is just a hunch (I'm not able to test anything right now). Look at code for deleting a specific node from a tree. If you always delete the root node, and rotate the left/right subtrees correctly, you will eventually bring the lower nodes up towards the top and delete everything.

**MutantJohn** · 10-30-2013

I'm not gonna lie, I'm surprised you can even allocate a tree so deep without overflowing the stack in the first place. How does that work? Are you not starting at the root and working your way down?

**oogabooga** · 10-30-2013

Originally Posted by MutantJohn

I'm not gonna lie, I'm surprised you can even allocate a tree so deep without overflowing the stack in the first place. How does that work? Are you not starting at the root and working your way down?

Tree nodes are not usually allocated on the stack !?
EDIT: Oh, I see what you mean!

As for the OP's question, one possibility is to store a parent pointer in the nodes.

**MutantJohn** · 10-30-2013

Lol my bad, I meant a recursive traversal just to allocate nodes on the heap in the first place.

And yeah, I was also thinking about suggesting a parent pointer as well because, well, it works but I'm not sure if it's the most elegant solution in terms of memory usage. Granted, it's only an extra 4 or 8 bytes per node but that can add up to be a lot.

**oogabooga** · 10-30-2013

Originally Posted by MutantJohn

I was also thinking about suggesting a parent pointer as well because, well, it works but I'm not sure if it's the most elegant solution in terms of memory usage. Granted, it's only an extra 4 or 8 bytes per node but that can add up to be a lot.

At least it's not stack memory, though.

anduril's solution is quite nifty. I think I'll give it a go.

**anduril462** · 10-30-2013

Originally Posted by oogabooga

As for the OP's question, one possibility is to store a parent pointer in the nodes.

Don't I feel an idiot for missing the obvious. Actually, parent pointers occurred to me in the middle or writing a sentence in my reply. I was certain I could remember it for a few seconds. Guess I'm older than I thought...

A fourth idea, if you know the tree will have a fairly fixed large number of nodes, one can increase the stack size. This is OS specific, ulimit -s will do it in most (all?) *NIX systems.

Originally Posted by MutantJohn

Lol my bad, I meant a recursive traversal just to allocate nodes on the heap in the first place.

I think you know all this, but just for clarity's sake: The word you're looking for is insert, not allocate. All allocation is on the heap, and no recursion is required. Presumably a recursive insert would also exceed stack limits, but iterative insert is easy to implement, compared to iterative delete.

**oogabooga** · 10-30-2013

@anduril,
Have you heard of PGS_MEM_Free before? I was wondering where it comes from.
It's mentioned here SDP Toolkit Primer for the ECS Project (section 6).

I'm finding your other idea difficult to implement. Looks like it'll involve rotations.

**anduril462** · 10-30-2013

Originally Posted by oogabooga

@anduril,
Have you heard of PGS_MEM_Free before? I was wondering where it comes from.
It's mentioned here SDP Toolkit Primer for the ECS Project (section 6).

No. I'll have to give it a look tonight when I have a little more time. That's NASA code, huh? I'm going to pretend we're helping with code for a space shuttle or rover.

Originally Posted by oogabooga

I'm finding your other idea difficult to implement. Looks like it'll involve rotations.

Yes, it does. I wont get a chance to toy with it myself for a few more hours at least, so I can only say that the rough algorithm I have in my head seems easy enough to implement iteratively. On the plus side, since we're deleting the whole tree, it doesn't matter how you rotate (e.g. always promote left child until there are none), since you don't need to maintain any order or balance. That might make things easier.

**oogabooga** · 10-30-2013

Originally Posted by anduril462

the rough algorithm I have in my head seems easy enough to implement iteratively. On the plus side, since we're deleting the whole tree, it doesn't matter how you rotate (e.g. always promote left child until there are none), since you don't need to maintain any order or balance. That might make things easier.

It was easy!

**iMalc** · 10-31-2013

Actually, this is dead-easy. Simple pseudocode follows:

Code:

While the root is not null
    if the left node of the root is not null
        perform a right rotation about the root
    else
        delete the root, replacing it with what was the right child of root
Done

**MutantJohn** · 10-31-2013

Lol what's a "right rotation"? Could you post or private message me some small example code? I mean, this isn't homework for me, I'm just genuinely curious.

**anduril462** · 10-31-2013

Originally Posted by MutantJohn

Lol what's a "right rotation"? Could you post or private message me some small example code? I mean, this isn't homework for me, I'm just genuinely curious.

Let me Google that for you