Deleting Leaf Nodes In A Binary Tree

Deleting leaf nodes with a given data in a binary tree


C++ : Deleting leaf nodes with a given data in a binary tree

#include<iostream>
using namespace std;

class Node {

    public:
    int data;
    Node * left;
    Node * right; 
    Node(int x) : data(x), left(NULL), right(NULL)
    {}
};

class Tree {

    public:
    /* Pre-order traversal to print the tree */
    void PreOrder(Node * node) {

         if(node != NULL) {
            cout << node->data << " ";
            PreOrder(node->left);
            PreOrder(node->right);
         }
    }

    bool CanRemove(Node * node, int target) {

        /* A matching leaf node */
        if (node->left == NULL and node->right == NULL and node->data == target) {
            return true;
        }

        if (node->left != NULL and CanRemove(node->left, target) == true) {
            delete node->left;
            node->left = NULL;
        }

        if (node->right != NULL and CanRemove(node->right, target) == true) {
            delete node->right;
            node->right = NULL;
        }
        /* Node's left and right children are deleted (thus node has become a leaf)
           also node's data matches with the target */
        if (node->left == NULL and node->right == NULL and node->data == target) {
            return true;
        }

        return false;
    }

    Node* RemoveLeafNodes(Node* root, int target) {

        cout << "\nRemoving leaves with data : " << target << endl;

        if (root == NULL)
            return NULL;

        if (root->left != NULL and CanRemove(root->left, target) == true) {
            delete root->left;
            root->left = NULL;
        }

        if (root->right != NULL and CanRemove(root->right, target) == true) {
           delete root->right;
           root->right = NULL;
        }

        /* Root's left and right children are deleted (thus root has become a leaf)
           also root's data matches with the target */
        if (root->left == NULL and root->right == NULL and root->data == target) {
           delete root;
           root = NULL;
        }

        return root;
    }
};

int main() {
    /*   1
        / \
       2   3 
      /   / \
     2   2   4  */

    Node * root1 = new Node(1);
    root1->left = new Node(2);
    root1->right = new Node(3);
    root1->left->left = new Node(2);
    root1->left->right = NULL;
    root1->right->left = new Node(2);
    root1->right->right = new Node(4);

    Tree t;

    cout << "Tree data (in pre-order) : [ ";
    t.PreOrder(root1); cout << "]";
    root1 = t.RemoveLeafNodes(root1, 2);
    cout << "Tree data (in pre-order) after leaves removal : [ ";
    t.PreOrder(root1); cout << "]\n";

    /*   1
        / \
       1   1  */

    Node * root2 = new Node(1);
    root2->left = new Node(1);
    root2->right = new Node(1);

    cout << "\nTree data (in pre-order) : [ ";
    t.PreOrder(root2); cout << "]";
    root2 = t.RemoveLeafNodes(root2, 1);
    cout << "Tree data (in pre-order) after leaves removal : [ ";
    t.PreOrder(root2); cout << "]";

    return 0;
}

Output of deleting nodes in a binary tree implemented in C++11

Tree data (in pre-order) : [ 1 2 2 3 2 4 ]
Removing leaves with data : 2
Tree data (in pre-order) after leaves removal : [ 1 3 4 ]

Tree data (in pre-order) : [ 1 1 1 ]
Removing leaves with data : 1
Tree data (in pre-order) after leaves removal : [ ]

Copyright © 2020, Algotree.org.
All rights reserved.