Like Tree3Likes

non-recursive free of binary tree

This is a discussion on non-recursive free of binary tree within the C Programming forums, part of the General Programming Boards category; Hello, I have a very deep binary tree to delete and I'm getting a stack overflow using the usual recursive ...

  1. #1
    Registered User
    Join Date
    Oct 2013
    Posts
    3

    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

  2. #2
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,496
    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.
    Last edited by anduril462; 10-30-2013 at 06:25 PM.

  3. #3
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,075
    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?

  4. #4
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by MutantJohn View Post
    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.
    Last edited by oogabooga; 10-30-2013 at 06:56 PM.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  5. #5
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,075
    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.

  6. #6
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by MutantJohn View Post
    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.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  7. #7
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,496
    Quote Originally Posted by oogabooga View Post
    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 View Post
    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.

  8. #8
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    @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.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  9. #9
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,496
    Quote Originally Posted by oogabooga View Post
    @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 View Post
    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.

  10. #10
    - - - - - - - - oogabooga's Avatar
    Join Date
    Jan 2008
    Posts
    2,808
    Quote Originally Posted by anduril462 View Post
    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!
    anduril462 likes this.
    The cost of software maintenance increases with the square of the programmer's creativity. - Robert D. Bliss

  11. #11
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    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
    vart likes this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  12. #12
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,075
    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.

  13. #13
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,496
    Quote Originally Posted by MutantJohn View Post
    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
    MutantJohn likes this.

  14. #14
    Registered User MutantJohn's Avatar
    Join Date
    Feb 2013
    Posts
    1,075
    I mean, I lol'd but omfg, Lord forbid I was hoping for some human interaction XD

  15. #15
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 7
    Last Post: 03-28-2013, 05:58 PM
  2. Recursive Binary Tree
    By Sorinx in forum C Programming
    Replies: 12
    Last Post: 11-10-2012, 09:27 AM
  3. recursive vs nonrecursive binary tree traversal
    By gaurav9991 in forum C Programming
    Replies: 4
    Last Post: 05-05-2011, 12:28 PM
  4. Free Binary tree
    By wirefree101 in forum C Programming
    Replies: 1
    Last Post: 12-06-2009, 05:13 PM
  5. binary tree but iterative, not recursive!
    By budala in forum C Programming
    Replies: 2
    Last Post: 08-06-2009, 12:55 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21