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

On Fri, 23 Nov 2007 17:14:39 -0800, Ben Pfaff wrote:

"jehugaleahsa@xxxxxxxxx" <jehugaleahsa@xxxxxxxxx> writes:

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.

There's no need to use level order for that. I would do it like this:
http://adtinfo.org/libavl.html/Destroying-a-BST-by-Rotation.html

To honor Ben Pfaff's grape-vine, here is my implementation with handles:

struct node {
struct node *nul,*one;
void *payload;
};

void node_eat_tree_by_vinification(struct node **root)
{
struct node *this,*temp;

while (*root) {
this = *root;
if (!this->nul) { *root=this->one;
free(this->payload); free(this); continue; }
temp = this->nul;
this->nul = temp->one;
temp->one = this;
*root = temp;
}
}

AvK

.

Relevant Pages

  • Re: linked list error
    ... main returns int. ... typedef int datatype; ... struct node *addtolist(struct node *root, ...
    (comp.lang.c)
  • Re: Problem with a linked list
    ... > Now in the printList method, the nothing is being printed, but ... typedef int datatype; ... struct node *next; ... struct node *addtolist(struct node *root, ...
    (comp.lang.c)
  • Re: some interview questions.
    ... Keep a pointer to the head of the list, ... struct node *next; ... static struct node *revlist(struct node *root) ...
    (comp.lang.c)
  • Re: linked list
    ... typedef int datatype; ... struct node *next; ... struct node *addtolist(struct node *root, ... struct node *newnode; ...
    (comp.lang.c)
  • can anyone tell me if this is useful to anyone
    ... I have been writing some string manipulation routines, ... struct occurence *next; ... struct Node *left; ... n = root; ...
    (comp.programming)