Member Avatar for em_jay

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 by happygeek because: fixed formatting
  • 3 Contributors
  • 2 Replies
  • 1K Views
  • 3 Years Discussion Span
  • Latest Post Latest Post by shroog

Dani AI

Generated

The root cause in 's snippet is that delete p runs for every node after the recursive calls, which frees the whole tree and leaves parents with dangling child pointers. was right that the parent's pointer must be updated when a child is deleted. The reliable ways are: return the (possibly NULL) subtree root from the recursive call, or operate on a reference / pointer-to-pointer so you can set the parent's child to NULL at the time of deletion.

To remove only the nodes that are leaves at the time the function is called (one pass, parents that become leaves are kept), check each child before recursing:

tree_node* remove_current_leaves(tree_node* node) {
    if (node == nullptr) return nullptr;

    if (node->left) {
        if (!node->left->left && !node->left->right) {
            delete node->left;
            node->left = nullptr;
        } else {
            remove_current_leaves(node->left);
        }
    }

    if (node->right) {
        if (!node->right->left && !node->right->right) {
            delete node->right;
            node->right = nullptr;
        } else {
            remove_current_leaves(node->right);
        }
    }

    return node;
}

// wrapper:
void removeLeaves() {
    if (root && !root->left && !root->right) { delete root; root = nullptr; return; }
    remove_current_leaves(root);
}

If the goal is to prune repeatedly (delete leaves, then newly-formed leaves, etc., until the subtree is gone), use a post-order that returns the new subtree root:

tree_node* prune_leaves(tree_node* node) {
    if (node == nullptr) return nullptr;
    node->left = prune_leaves(node->left);
    node->right = prune_leaves(node->right);
    if (!node->left && !node->right) { delete node; return nullptr; }
    return node;
}

// wrapper:
root = prune_leaves(root);

Notes: choose nullptr or NULL to match your C++ standard. Both approaches are O(n) time; recursion depth is the tree height. If you try a non-recursive implementation like , be careful with parent lookup (avoid using stale parent pointers or calling parent() after you've modified the tree). Always set deleted child pointers to NULL to prevent double-free or use-after-free bugs.

Recommended Answers

All 2 Replies

Member Avatar for stilllearning

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.

Member Avatar for shroog

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;}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.