Binary Search Trees: Given a BST, remove all the leaf nodes

Problem Statement:

Given a BST, remove all the leaf nodes

Example:

Input:

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

Output:

    /*
     *           10
     *         /    \
     *        8      12
     */

Solution Explanation:

Do inroder traversal on the tree.

Check if its a leaf node, if yes, delete it.

Else proceed with left and right children.

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

Code Solution

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

class Tree_Node 
{
public:
	int data;
	Tree_Node* left;
	Tree_Node* right;

	Tree_Node(int x) 
	{
		data = x;
		left = nullptr;
		right = nullptr;
	}
};

void inorderTraversal(Tree_Node* root)
{
    if (!root)
        return;
    inorderTraversal(root->left);
    cout<<root->data<< " " ;
    inorderTraversal(root->right);
}

Tree_Node* solution(Tree_Node* root) 
{

    if (root == nullptr)
        return nullptr;

    if (root->left == nullptr && root->right == nullptr) 
    {
        delete root;
        return nullptr;
    }

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

    return root;
}


int main()
{

    /*
     *           10
     *         /    \
     *        8      12
     *       / \    /  \
     *      2   9  11   14
     */
    Tree_Node* root = new Tree_Node(10);
    root->left = new Tree_Node(8);
    root->right = new Tree_Node(12);
    root->left->left = new Tree_Node(2);
    root->left->right = new Tree_Node(9);
    root->right->left = new Tree_Node(11);
    root->right->right = new Tree_Node(14);
    
    solution(root);
    inorderTraversal(root);

    return 0;
}

Output

8 10 12