CODEWITHSUNDEEP
cpointersstructbinary-search-tree
DewinDell
DewinDell

Reputation: 1028

removing leaves doesn't affect a BST - C

I wrote a function to nullify all the leaves of a BST. The BST has a left and right pointer of course and a char called data to store the value of the node.

void removeLeaves(struct Tree* T){
  if(T->left == NULL && T->right == NULL){
    printf("removing %c\n", T->data);
    T=NULL;
  }
  else{
    if(T->left!=NULL){
      removeLeaves(T->left);
    }
    if(T->right!=NULL){  
      removeLeaves(T->right);
    }
  }  
}

I Print the tree before and after envoking this function. And although the print statement above works and prints the nodes that are nullified, the resulting tree is the same. I have something like:

print(BST);
removeLeaves(BST);
print(BST);

Any idea what's going on? Thanks.

Upvotes: 4

Views: 158

Answers (3)

John3136
John3136

Reputation: 29266

You are passing T by value, so setting T to null does nothing (T is just a local copy of the pointer).

You need some way of setting T's 'owner' (i.e. parent->left or parent->right) to null.

(Also by setting T to null you risk a memory leak - do you need to free()?)

Upvotes: 1

thb
thb

Reputation: 14454

You have the parts you need. It's mostly a matter of reordering them.

void removeLeaves(struct Tree* const T){
  if(T->left!=NULL){
    removeLeaves(T->left);
    T->left = NULL;
  }
  if(T->right!=NULL){  
    removeLeaves(T->right);
    T->right = NULL;
  }
}

Note however the const. Your code can work without it, but it shouldn't, because setting T = NULL doesn't actually do anything, although one might thing that it would.

Update: @PaulP.R.O.'s answer is interesting, incidentally. I prefer mine, but you can try both and see which suits.

By the way, be sure that you don't need a call to free() in there somewhere, to prevent a memory leak.

Upvotes: 0

Paul
Paul

Reputation: 141827

T=NULL; assigns null to a local pointer, not to anything in your tree. You need to use a struct Tree ** so that you can modify the struct Tree *:

void removeLeaves(struct Tree ** T){
  if((*T)->left == NULL && (*T)->right == NULL){
    printf("removing %c\n", (*T)->data);
    *T = NULL;
  }
  else{
    if((*T)->left!=NULL){
      pruneTree((*T)->left);
    }
    if((*T)->right!=NULL){  
      pruneTree((*T)->right);
    }
  }  
}

Upvotes: 1

Related Questions