Binary Tree Pruning

Before going to the Binary Tree Pruning Code, you should know what is pruning. So, Binary tree pruning is the process where we remove certain nodes from a binary tree based on a specific condition.

Question:

In this question, our main objective is to remove unnecessary nodes from the tree according to the question to optimize the tree structure.

Binary Tree Pruning helps us to:

1. It easily simplifies the tree structure.
2. Also, it reduces the size of the tree.
3. Remove unused nodes that do not need for the desired output.

In this blog, we are removing all the nodes that have a value of 0.

Code:

The specific pruning condition code can vary depending on the problem. Here, we have taken common conditions that involve removing nodes with 0 value.
Note: We can’t remove that node with a 0 value that has a child node with a value other than 0. If we do so, then we will destroy the whole subtree and will not be able to maintain the tree’s actual accuracy.

#include <iostream>

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int value) : val(value), left(nullptr), right(nullptr) {}
};

TreeNode* pruneTree(TreeNode* root) {
    if (root == nullptr) {
        return nullptr;
    }

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

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

    return root;
}

void printInorder(TreeNode* root) {
    if (root != nullptr) {
        printInorder(root->left);
        std::cout << root->val << " ";
         printInorder(root->right);
    }
}

int main() {
    // Create a sample binary tree
    TreeNode* root = new TreeNode(3);
    root->left = new TreeNode(0);
    root->right = new TreeNode(1);
    root->left->left = new TreeNode(2);
    root->left->right = new TreeNode(0);
    root->right->left = new TreeNode(0);
    root->right->right = new TreeNode(1);
    root->right->right = new TreeNode(5);

    std::cout << "Original Tree: ";
    printInorder(root);
    std::cout << std::endl;

    // Prune the binary tree
    TreeNode* prunedTree = pruneTree(root);

    std::cout << "Pruned Tree: ";
    printInorder(prunedTree);
    std::cout << std::endl;

    // Clean up the memory
    delete prunedTree;
    prunedTree = nullptr;

    return 0;
}

Explanation of the Code:

So, here is the explanation of the code:

1. Firstly, we define a TreeNode structure that represents the nodes of the binary tree. Each node has an integer value (val) and pointers to its left and right child nodes (left and right).
2. After that, we will make a pruneTree function that takes a TreeNode* root as the input parameter and returns the pruned tree. After this, we perform the pruning process recursively for every node.
3. In the pruneTree function,
   • First, we check if the root pointer is nullptr or not, which indicates it is an empty tree. If it is null, then we return nullptr indicating that there is no tree to do prune operations.
   • Secondly, if the root value is not nullptr, we recursively prune the left and right subtrees by calling the pruneTree function recursively.
   • This two-step will ensure that all nodes in the tree are pruned properly according to the condition.
4. After pruning the subtrees, we check whether the current root node needs to be pruned or not according to the question. So, to do so, we will check three conditions mentioned below:
   • If the left child and right child of the current node are both nullptr and the value of the current node is 0, then it means the node is a leaf node with a value of 0 and it should be pruned.
   • If the current node satisfies the pruning conditions, we delete the root node using the delete keyword, which deallocates the memory for that node and returns nullptr to indicate that this node has been pruned properly from the tree.
   • If the current node does not satisfy the pruning conditions, we simply return the root node, as it does not need to be pruned because it does not satisfy the condition.
5. Then, we make another printInorder function to print the nodes of the binary tree in the inorder traversal. It will recursively traverses the tree and prints the values of the nodes.
6. We make another main function, here we create a sample binary tree with a specific structure and node values.
7. We then print the original tree using the printInorder function.
8. Next, we call the pruneTree function to prune the binary tree. And will assign the value of the pruned tree node to the variable “prunedTree”.
9. Finally, We print the pruned tree using the printInorder function.
10. After this, we clean up the memory by deleting the pruned tree and setting the prunedTree pointer to nullptr.

Summary:

The binary tree pruning process involves traversing the nodes of the binary tree, either recursively or iteratively, and evaluating each node against the pruning condition. If a node satisfies the condition, we will remove that node. Else, it will remain the same.