Algotree > Algorithms > Tree & Graph Traversal > Deleting Leaf Nodes In A Binary Tree

Deleting Leaf Nodes In A Binary Tree

The idea behind deleting the leaf nodes (of a specific value) in a binary tree is to use a recursive algorithm as the same logic should be applied to the root as well as to all the other nodes in the tree. The recursive algorithm is as follows :

If the root is null, then there is nothing to be done so we return.
Traverse the left sub-tree of the root all the way down till a leaf node is found, and see if it could be deleted.
- If a matching leaf node is found, delete it and return a null pointer. This null pointer is returned to the parent of the deleted leaf node so that parent’s left could be updated.
Traverse the right sub-tree of the root all the way down till a leaf node is found, and see if it could be deleted.
- If a matching leaf node is found, delete it and return a null pointer. This null pointer is returned to the parent of the deleted leaf node so that parent’s right could be updated.
Check if the root node could be deleted. i.e If root’s left child and right child are null and root matches with the given value, delete root.
Return root.

Delete Leaf Nodes In 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, Node *left = nullptr, Node * right = nullptr) {
        data = x;
    }
};

class Tree {

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

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

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

        // Root is nullptr, there is nothing to be deleted.
        if (root == nullptr)
            return nullptr;

        // If root's left child gets deleted, root's left should be updated.
        root->left  = RemoveLeafNodes(root->left, target);

        // If root's right child gets deleted, root's right should be updated.
        root->right = RemoveLeafNodes(root->right, target);

        if (root->left == nullptr && root->right == nullptr && root->data == target){
            cout << "\nRemoving leaf node with data : " << target;
            delete root;
            return nullptr;
        }
        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 = nullptr;
    root1->right->left = new Node(2);
    root1->right->right = new Node(4);

    Tree t;

    cout << "\nTree data (in pre-order) : [ ";
    t.PreOrder(root1); cout << "]";
    root1 = t.RemoveLeafNodes(root1, 2);
    cout << "\nTree 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 << "\nTree data (in pre-order) after leaves removal : [ ";
    t.PreOrder(root2); cout << "]";

    return 0;
}

Output

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

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