Binary Tree: Given a binary tree and a target, delete leaf nodes having value target

Problem Statement:

Given a binary tree and a target, delete leaf nodes having value target

Example:

Input: 

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

Target = 14

Output:

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

Solution Explanation:

We will solve the problem using post order, depth first search traversal.

Recursively call the recursion function on left and right children.

If if the node is a leaf and the value is equal to target, delete it.

Time Complexity: O(n)
Space Complexity: O(logn)

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);
}


void insert_inorder(Node* root, vector<int>& nodes) 
{
    if (root == nullptr) 
    {
        return;
    }
  
    insert_inorder(root->left, nodes);  
    nodes.push_back(root->data);          
    insert_inorder(root->right, nodes); 
}

Node* solution(Node* root, int target) 
{
    if (!root) 
        return nullptr;

    root->left = solution(root->left, target);
    root->right = solution(root->right, target);

    if (!root->left && !root->right && root->data == target)
        return nullptr;
    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