Binary Tree: Given a tree, delete leaf nodes with value k

Problem Statement:

You are given a tree and a value k.

You need to delete all the leaf nodes with the given value

Example:

Input:

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */

K = 14



Output:

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  
     *      2   9  11  
     */

Solution Explanation:

It is important to observe that we need to delete the leaf nodes.

We must process the tree bottom up.

So we need to use post order traversal to solve the issue.

Traverse the tree in postorder traversal.

Then delete the nodes recursively if the value is equal to k.

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node 
{
    int data;
    struct Node *left;
    struct Node *right;
};


struct Node* newNode(int data)
{
    struct Node* newNode = new Node;
    newNode->data = data;
    newNode->left = newNode->right = NULL;

    return (newNode);
}

void display_inorder(Node* root)
{
    if (root == NULL)
        return;

    display_inorder(root->left);
    cout << root->data << " ";
    display_inorder(root->right);
}

Node *solution(Node * root, int key)
{
    if(root==NULL) 
    	return NULL;
    

    root->left = solution(root->left, key);
    root->right = solution(root->right, key);
    
    if(root->left==NULL && root->right==NULL && root->data == key)
    {
        return NULL;
    }
    return root;
}



int main(void)
{
    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    struct Node* root = newNode(10);
    root->left = newNode(8);
    root->right = newNode(12);
    root->left->left = newNode(2);
    root->left->right = newNode(9);
    root->right->left = newNode(11);
    root->right->right = newNode(14);

    solution(root, 14);
    
    cout << "Inorder traversal after deletion : ";
    display_inorder(root);
    return 0;
}

Output

Inorder traversal after deletion : 2 8 9 10 11 12