non-recursive free of binary tree

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

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.

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?

Quote:

---

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.

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.

Quote:

---

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.

Quote:

---

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.

Quote:

---

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.

@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.

Quote:

---

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.

Quote:

---

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.

Quote:

---

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! :)

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

---

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.

Quote:

---

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

I mean, I lol'd but omfg, Lord forbid I was hoping for some human interaction XD

https://en.wikipedia.org/wiki/Tree_rotation

I kind of get it but hoo boy is that weird. I don't even know if I could code that. It's hard enough just to do on paper. Talk about messing with my mind.

Also, is it possible to rotate higher order trees? Like an octree or a quadtree? A google search seems to indicate that there isn't a way, is there?

Quote:

---

Originally Posted by MutantJohn

I kind of get it but hoo boy is that weird. I don't even know if I could code that. It's hard enough just to do on paper. Talk about messing with my mind.

Also, is it possible to rotate higher order trees? Like an octree or a quadtree? A google search seems to indicate that there isn't a way, is there?

---

The general term for describing a tree with n children per node is n-ary (or k-ary, k-way, etc); when the number of children is known, you can say a 4-ary or 8-ary tree. Quadtrees and octrees are generally understood to be specific kinds of 4-ary and 8-ary trees, respectively, that are used for partitioning (e.g. 2-d and 3-d regions respectively). Note, an n-ary tree can also refer to a tree where each node is allowed to have any number of children. Also, remember, a tree is more or less just a graph with no cycles (usually a directed graph with each node having just one parent, and the root of the tree has no incoming edges).

For trees with more than two children per node, it's less clear on what a rotate would consist of. Since there's not just a left and right child, which of the 3, 4, 8, etc, children would you rotate to the root? Which node does the former root become a child of? Theoretically you could reorder any tree, moving a child node up to the root and moving the root down (it's just swapping some pointers around), but I'm not sure I would call it a "rotate". Perhaps a "restructure" would be more appropriate. Whether the resulting tree is of any use is another question. A big part of whether you can usefully restructure a tree, and how you would do so, would depend on the constraints of your tree: ordering of nodes in your tree, balance requirements, relationships between parent and child nodes, etc. A quadtree or octree can not be be restructured (short of swapping sibling nodes, which is trivial and does not fundamentally alter the tree) and maintain it's spatial hierarchy. Other trees, maybe. It would take me a while to churn through a bunch of n-ary tree structures to see if I can find an example that is restructure-able. Not sure if I'll have time today.

Yes, it is NASA code, but for something as mundane as an earth-observing satellite. Sorry, nothing as exciting as a space shuttle or rover. And nothing falls out of the sky if this code doesn't work, as it's part of the ground processing system.

Thank-you. All coded, tested to the n-th degree, and it works like a charm! Very clever solution and very simple also. That's the best kind!

Catherine

Quote:

---

Originally Posted by iMalc

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

---

---

Quote:

---

Originally Posted by cmoroney

Yes, it is NASA code, but for something as mundane as an earth-observing satellite. Sorry, nothing as exciting as a space shuttle or rover. And nothing falls out of the sky if this code doesn't work, as it's part of the ground processing system.

---

I figured this was some library available to the public, and you were just using it for some personal project. Not mundane. Satellites are way more awesome than the stuff I work on normally.