I need help in deleting all the leaf nodes in BST

void BinarySearchTree::removeLeaves()
{
  removeleaf(root);
}

void BinarySearchTree::removeleaf(tree_node* p)
{   
    if(p != NULL)
    {   

        if(p->left) removeleaf(p->left);
        if(p->right) removeleaf(p->right);
        delete p; 


    }
    else return;
}

can someone check my code.
pls

Edited 3 Years Ago by happygeek: fixed formatting

Well what you are doing will recursively delete all the nodes.

If you want to delete only current leaves, then you need to do something like this. I haven't tested this, so please try it out.

void BinarySearchTree::removeleaf(tree_node* p){
if (p == NULL){
    return;
  }
  else{
    if (p->left || p->right){
      removeLeaf(p->left);
      removeLeaf(p->right);
    }
    else{
      delete p; 
      return; 
    }
  }

You have to make sure that p gets set to null after its deleted.

pls I need help to know what is wrong in my cod
This cod will insert BST , traversal Inorder and deleting(leaf/node has 1child/has 2child) ..
With non_recursive method !!

#include<iostream>
using namespace std;
struct tn{
    int key;
    tn *left;
    tn *right;};
    class tree{
    private:

        tn *root;
    public:
        tn *search(int x){
            tn *p=root;
            while(p->key!=x){
                if(p->key<x)
                    p=p->right;
                else if(p->key>x)
                    p=p->left;}

            return p;}
        tn *getroot(){
            return root;}

        bool isEmpty(){
            return( root==NULL);}
        bool leaf(tn *p){
            return(p->left==NULL&&p->right==NULL);}
        tree(){
            root=NULL;}
        int count(tn *p){
            if(p==NULL) return 0;
            return 1+count(p->left)+count(p->right);}
        void inorder(tn *p){
            if(p){
                inorder(p->left);
                cout<<p->key<<"  ";
                inorder(p->right);
        }
        }
        tn *parent(tn *q){
            tn *p=root;
            tn *parent;
            {

                while(p){
                parent=p;
                if(q->key<p->key)
                    p=p->left;
                else if(q->key>p->key)
                    p=p->right;}
            return parent;
            }}
        void inseart(int x){
            tn *q=new tn;
            q->key=x;
            q->left=NULL;
            q->right=NULL;

            if(isEmpty()) root=q;
            else{
                tn *par=parent(q);

                if(par->key<q->key)
                    par->right=q;
                else
                    parent(q)->left=q;
            }
        }
        //methods for deletion :.
        void dleaf(tn *p){

            cout<<"\nparent=  "<<parent(p)->key;

            if(p->key>parent(p)->key){

                delete p;
                parent(p)->right=NULL;
                cout<<"\nr:";
            }
            if(p->key<parent(p)->key){

                delete p;
            parent(p)->left=NULL;}
        }
        void d1child(tn *p){
            tn *par=parent(p);
            if(p->left==NULL){
                if(par->right==p){
                    par->right=p->right;
                    delete p;}
                else if(par->left==p){
                    par->left=p->right;
                    delete p;}
            }
            else if(p->right==NULL){
                if(par->right==p){
                    par->right=p->right;
                    delete p;}
                else if(par->left==p){
                    par->left=p->right;
                    delete p;}}
        }
        tn *pre(tn *q){
            if(q->left==NULL){
                cout<<"no pre.. return :";
                return q;}
            if(q->left!=NULL){
                q=q->left;
            while(q->right!=NULL){
                q=q->right;}}
            return q;} 
        tn *suc(tn *q){
            if(q->right==NULL){
                cout<<"no suc.. return :";
                return q;}
            if(q->right!=NULL){
                q=q->right;
            while(q->left!=NULL){
                q=q->left;}}
            return q;}
        void d2kids(tn *p){
            tn *q;
                q=pre(p);
                p->key=q->key;
                if(leaf(q))
                     dleaf(q);
                else
                    d1child(q);}
        void droot(tn *p){
            tn *q;
            q=suc(p);
            root->key=q->key;
            if(leaf(q))
                dleaf(q);
            else
                d1child(q);}
void del(tn *p){
    if(isEmpty())
        cout<<"It Is an Empty Tree";
    else if(leaf(p)){
        cout<<"d leaf";
        dleaf(p);}
    else if(p->right!=NULL || p->left!=NULL)
        d1child(p);
    else if(p->right!=NULL && p->left!=NULL)
        d2kids(p);
    else if(p==root)
        droot(p);
}

    };

    int main(){
        tree t;
        int y,x,ch;
        cout<<"enter your choice //must be >0 && <6 :(6-Exit )\n ";
        cin>>ch;
        while(ch!=6){
            if(ch==1)
            {cout<<"enter value:   ";
            cin>>x;
            t.inseart(x);
            cin>>ch;}
            if(ch==2){
                cout<<"\nyour Element :\n";

                t.inorder(t.getroot());
                cin>>ch;
            }
            if(ch==3){
                cout<<"\nWhich Element you want to deleted ?  ";
                cin>>y;
                t.del(t.search(y));
                cout<<"\n Your element After deletion\n";
                t.inorder(t.getroot());
                cin>>ch;}
        }
        return 0;}
This article has been dead for over six months. Start a new discussion instead.