Eliminar Nodes en caminos de raíz a hoja de longitud < K

Dado un árbol binario y un número k, elimine todos los Nodes que se encuentran solo en la ruta (s) de raíz a hoja de longitud menor que k. Si un Node X se encuentra en varias rutas de raíz a hoja y si alguna de las rutas tiene una longitud de ruta >= k, entonces X no se elimina del árbol binario. En otras palabras, un Node se elimina si todos los caminos que lo atraviesan tienen longitudes menores que k.

Considere el siguiente ejemplo de árbol binario 

// C++ program to remove nodes on root to leaf paths of length < K
#include<bits/stdc++.h>
using namespace std;
  
struct Node
{
    int data;
    Node *left, *right;
};
  
//New node of a tree
Node *newNode(int data)
{
    Node *node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
  
// Utility method that actually removes the nodes which are not
// on the pathLen >= k. This method can change the root as well.
Node *removeShortPathNodesUtil(Node *root, int level, int k)
{
    //Base condition
    if (root == NULL)
        return NULL;
  
    // Traverse the tree in postorder fashion so that if a leaf
    // node path length is shorter than k, then that node and
    // all of its descendants till the node which are not
    // on some other path are removed.
    root->left = removeShortPathNodesUtil(root->left, level + 1, k);
    root->right = removeShortPathNodesUtil(root->right, level + 1, k);
  
    // If root is a leaf node and it's level is less than k then
    // remove this node.
    // This goes up and check for the ancestor nodes also for the
    // same condition till it finds a node which is a part of other
    // path(s) too.
    if (root->left == NULL && root->right == NULL && level < k)
    {
        delete root;
        return NULL;
    }
  
    // Return root;
    return root;
}
  
// Method which calls the utility method to remove the short path
// nodes.
Node *removeShortPathNodes(Node *root, int k)
{
    int pathLen = 0;
    return removeShortPathNodesUtil(root, 1, k);
}
  
//Method to print the tree in inorder fashion.
void printInorder(Node *root)
{
    if (root)
    {
        printInorder(root->left);
        cout << root->data << " ";
        printInorder(root->right);
    }
}
  
// Driver method.
int main()
{
    int k = 4;
    Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->left->left->left = newNode(7);
    root->right->right = newNode(6);
    root->right->right->left = newNode(8);
    cout << "Inorder Traversal of Original tree" << endl;
    printInorder(root);
    cout << endl;
    cout << "Inorder Traversal of Modified tree" << endl;
    Node *res = removeShortPathNodes(root, k);
    printInorder(res);
    return 0;
}

// Java program to remove nodes on root to leaf paths of length < k
   
/* Class containing left and right child of current 
   node and key value*/
class Node 
{
    int data;
    Node left, right;
   
    public Node(int item) 
    {
        data = item;
        left = right = null;
    }
}
   
class BinaryTree 
{
    Node root;
   
    // Utility method that actually removes the nodes which are not
    // on the pathLen >= k. This method can change the root as well.
    Node removeShortPathNodesUtil(Node node, int level, int k) 
    {
        //Base condition
        if (node == null)
            return null;
              
        // Traverse the tree in postorder fashion so that if a leaf
        // node path length is shorter than k, then that node and
        // all of its descendants till the node which are not
        // on some other path are removed.
        node.left = removeShortPathNodesUtil(node.left, level + 1, k);
        node.right = removeShortPathNodesUtil(node.right, level + 1, k);
   
        // If root is a leaf node and it's level is less than k then
        // remove this node.
        // This goes up and check for the ancestor nodes also for the
        // same condition till it finds a node which is a part of other
        // path(s) too.
        if (node.left == null && node.right == null && level < k)
            return null;
   
        // Return root;
        return node;
    }
   
    // Method which calls the utility method to remove the short path
    // nodes.
    Node removeShortPathNodes(Node node, int k) 
    {
        int pathLen = 0;
        return removeShortPathNodesUtil(node, 1, k);
    }
   
    //Method to print the tree in inorder fashion.
    void printInorder(Node node) 
    {
        if (node != null) 
        {
            printInorder(node.left);
            System.out.print(node.data + " ");
            printInorder(node.right);
        }
    }
   
    // Driver program to test for samples
    public static void main(String args[]) 
    {
        BinaryTree tree = new BinaryTree();
        int k = 4;
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.left.left.left = new Node(7);
        tree.root.right.right = new Node(6);
        tree.root.right.right.left = new Node(8);
        System.out.println("The inorder traversal of original tree is : ");
        tree.printInorder(tree.root);
        Node res = tree.removeShortPathNodes(tree.root, k);
        System.out.println("");
        System.out.println("The inorder traversal of modified tree is : ");
        tree.printInorder(res);
    }
}
   
// This code has been contributed by Mayank Jaiswal

# Python3 program to remove nodes on root 
# to leaf paths of length < K 
  
# New node of a tree 
class newNode: 
    def __init__(self, data): 
        self.data = data 
        self.left = self.right = None
          
# Utility method that actually removes 
# the nodes which are not on the pathLen >= k.
# This method can change the root as well. 
def removeShortPathNodesUtil(root, level, k) :
  
    # Base condition 
    if (root == None) :
        return None
  
    # Traverse the tree in postorder fashion 
    # so that if a leaf node path length is 
    # shorter than k, then that node and all 
    # of its descendants till the node which  
    # are not on some other path are removed. 
    root.left = removeShortPathNodesUtil(root.left, 
                                         level + 1, k) 
    root.right = removeShortPathNodesUtil(root.right, 
                                          level + 1, k) 
  
    # If root is a leaf node and it's level 
    # is less than k then remove this node. 
    # This goes up and check for the ancestor 
    # nodes also for the same condition till
    # it finds a node which is a part of other 
    # path(s) too. 
    if (root.left == None and
        root.right == None and level < k) : 
        return None
      
    # Return root 
    return root 
  
# Method which calls the utility method 
# to remove the short path nodes. 
def removeShortPathNodes(root, k) :
    pathLen = 0
    return removeShortPathNodesUtil(root, 1, k) 
  
# Method to print the tree in
# inorder fashion. 
def printInorder(root) :
  
    if (root) :
      
        printInorder(root.left) 
        print(root.data, end = " " )
        printInorder(root.right) 
      
# Driver Code 
if __name__ == '__main__':
    k = 4
    root = newNode(1) 
    root.left = newNode(2) 
    root.right = newNode(3) 
    root.left.left = newNode(4) 
    root.left.right = newNode(5) 
    root.left.left.left = newNode(7) 
    root.right.right = newNode(6) 
    root.right.right.left = newNode(8) 
    print("Inorder Traversal of Original tree" ) 
    printInorder(root) 
    print()
    print("Inorder Traversal of Modified tree" ) 
    res = removeShortPathNodes(root, k) 
    printInorder(res)
  
# This code is contributed 
# by SHUBHAMSINGH10

using System;
  
// C# program to remove nodes on root to leaf paths of length < k 
  
/* Class containing left and right child of current  
   node and key value*/
public class Node
{
    public int data;
    public Node left, right;
  
    public Node(int item)
    {
        data = item;
        left = right = null;
    }
}
  
public class BinaryTree
{
    public Node root;
  
    // Utility method that actually removes the nodes which are not 
    // on the pathLen >= k. This method can change the root as well. 
    public virtual Node removeShortPathNodesUtil(Node node, int level, int k)
    {
        //Base condition 
        if (node == null)
        {
            return null;
        }
  
        // Traverse the tree in postorder fashion so that if a leaf 
        // node path length is shorter than k, then that node and 
        // all of its descendants till the node which are not 
        // on some other path are removed. 
        node.left = removeShortPathNodesUtil(node.left, level + 1, k);
        node.right = removeShortPathNodesUtil(node.right, level + 1, k);
  
        // If root is a leaf node and it's level is less than k then 
        // remove this node. 
        // This goes up and check for the ancestor nodes also for the 
        // same condition till it finds a node which is a part of other 
        // path(s) too. 
        if (node.left == null && node.right == null && level < k)
        {
            return null;
        }
  
        // Return root; 
        return node;
    }
  
    // Method which calls the utility method to remove the short path 
    // nodes. 
    public virtual Node removeShortPathNodes(Node node, int k)
    {
        int pathLen = 0;
        return removeShortPathNodesUtil(node, 1, k);
    }
  
    //Method to print the tree in inorder fashion. 
    public virtual void printInorder(Node node)
    {
        if (node != null)
        {
            printInorder(node.left);
            Console.Write(node.data + " ");
            printInorder(node.right);
        }
    }
  
    // Driver program to test for samples 
    public static void Main(string[] args)
    {
        BinaryTree tree = new BinaryTree();
        int k = 4;
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);
        tree.root.left.left.left = new Node(7);
        tree.root.right.right = new Node(6);
        tree.root.right.right.left = new Node(8);
        Console.WriteLine("The inorder traversal of original tree is : ");
        tree.printInorder(tree.root);
        Node res = tree.removeShortPathNodes(tree.root, k);
        Console.WriteLine("");
        Console.WriteLine("The inorder traversal of modified tree is : ");
        tree.printInorder(res);
    }
}
  
  //  This code is contributed by Shrikant13

<script>
  
    // JavaScript program to remove nodes on 
    // root to leaf paths of length < k
      
    class Node
    {
        constructor(item) {
           this.left = null;
           this.right = null;
           this.data = item;
        }
    }
    
    let root;
     
    // Utility method that actually removes the nodes which are not
    // on the pathLen >= k. This method can change the root as well.
    function removeShortPathNodesUtil(node, level, k) 
    {
        //Base condition
        if (node == null)
            return null;
                
        // Traverse the tree in postorder fashion so that if a leaf
        // node path length is shorter than k, then that node and
        // all of its descendants till the node which are not
        // on some other path are removed.
        node.left = removeShortPathNodesUtil(node.left, level + 1, k);
        node.right = removeShortPathNodesUtil(node.right, level + 1, k);
     
        // If root is a leaf node and it's level is less than k then
        // remove this node.
        // This goes up and check for the ancestor nodes also for the
        // same condition till it finds a node which is a part of other
        // path(s) too.
        if (node.left == null && node.right == null && level < k)
            return null;
     
        // Return root;
        return node;
    }
     
    // Method which calls the utility method to remove the short path
    // nodes.
    function removeShortPathNodes(node, k) 
    {
        let pathLen = 0;
        return removeShortPathNodesUtil(node, 1, k);
    }
     
    //Method to print the tree in inorder fashion.
    function printInorder(node) 
    {
        if (node != null) 
        {
            printInorder(node.left);
            document.write(node.data + " ");
            printInorder(node.right);
        }
    }
      
    let k = 4;
    root = new Node(1);
    root.left = new Node(2);
    root.right = new Node(3);
    root.left.left = new Node(4);
    root.left.right = new Node(5);
    root.left.left.left = new Node(7);
    root.right.right = new Node(6);
    root.right.right.left = new Node(8);
    document.write("The inorder traversal of Original tree is : " + 
    "</br>");
    printInorder(root);
    let res = removeShortPathNodes(root, k);
    document.write("</br>");
    document.write("The inorder traversal of Modified tree is : " + 
    "</br>");
    printInorder(res);
      
</script>