Remove all leaf nodes from an n-ary tree

Given an n-ary tree, Our goal is to find and remove all leaf node which is present in given tree.

Deleting all leaf nodes in n-ary tree

Here given code implementation process.

import java.util.Vector;
// Java program for
// Remove all leaf nodes from a N-ary Tree
class TreeNode
{
    public int key;
    public Vector < TreeNode > child;
    public TreeNode(int key)
    {
        // Set node key
        this.key = key;
        // Create memory of TreeNode child
        this.child = new Vector < TreeNode > ();
    }
    public void addChild(int key)
    {
        // Create a new node
        TreeNode node = new TreeNode(key);
        // Add node into child
        this.child.add(node);
    }
}
public class NAryTree
{
    public TreeNode root;



    public NAryTree()
    {
       
        this.root = null;
   
    }
   
    public void deleteLeafNodes(TreeNode node )
    {
        if(node == null)
        {
            return;
        }
        
        int i = 0;

        TreeNode temp = null;

        while(i < node.child.size())
        {
            temp = node.child.get(i);

            if(temp.child.size()==0)
            {
                // When node is leaf node
                node.child.remove(i);
            }
            else
            {
                deleteLeafNodes(temp); 
                
                i++;
            }
        }

    }
    public void removeLeafNodes()
    {
      
        if(this.root == null )
        {
            // When tree is empty
            return;
        }
        if(this.root.child.size() == 0)
        {
            // When delete root node
            this.root = null;
        }
        else
        {
            // Find and remove leaf nodes
            this.deleteLeafNodes(this.root);
        }


    }


    public void printPreorder(TreeNode node )
    {
        if(node == null)
        {
            return;
        }
        
        int i = 0;

        TreeNode temp = null;

        System.out.print("  "+node.key);   

        // iterating the child of given node
        while(i < node.child.size())
        {
            temp = node.child.get(i);

            printPreorder(temp);

            i++;
        }


    }

    public static void main(String[] args)
    {
        NAryTree tree = new NAryTree();
        /*
                   10
                  /   \
                 /     \
                /       \   
               8         5
              /|\      /|\ \ 
             / | \    / | \ \
            -2 1  6  7 18 3  4
              / \     \     /| \
             9  11    -1   2 1  3
               /  \
              17   12   
            -----------------------
            Constructing N-Ary tree
        */
        // First element of tree
        tree.root = new TreeNode(10);
        tree.root.addChild(8);
        tree.root.addChild(5);
        // Add child node [-2,1,6] in node (8)
        tree.root.child.get(0).addChild(-2);
        tree.root.child.get(0).addChild(1);
        tree.root.child.get(0).addChild(6);
        // Add child node [9,11] in node (1)
        tree.root.child.get(0).child.get(1).addChild(9);
        tree.root.child.get(0).child.get(1).addChild(11);
        // Add child node [17  12] in node (11)
        tree.root.child.get(0).child.get(1).child.get(1).addChild(17);
        tree.root.child.get(0).child.get(1).child.get(1).addChild(12);
        // Add child node [7 18 3  4] in node (5)
        tree.root.child.get(1).addChild(7);
        tree.root.child.get(1).addChild(18);
        tree.root.child.get(1).addChild(3);
        tree.root.child.get(1).addChild(4);

        // Add child node [-1] in node (7)
        tree.root.child.get(1).child.get(0).addChild(-1);

        // Add child node [2,1,3] in node (4)
        tree.root.child.get(1).child.get(3).addChild(2);
        tree.root.child.get(1).child.get(3).addChild(1);
        tree.root.child.get(1).child.get(3).addChild(3);

        System.out.print("\n Before remove leaf nodes \n");
        tree.printPreorder(tree.root);
       
        // Remove leaf nodes
        tree.removeLeafNodes();

        System.out.print("\n After remove leaf nodes \n");

        /*
               10                
              /  \
             /    \   
            /      \   
           8        5          
           |       / \ 
           |      /   \
           1     7     4       
            \            
            11          
                           
        */
        // After remove leaf nodes
        tree.printPreorder(tree.root);
    }
}

Output

 Before remove leaf nodes
  10  8  -2  1  9  11  17  12  6  5  7  -1  18  3  4  2  1  3
 After remove leaf nodes
  10  8  1  11  5  7  4
package main
import "fmt"
// Go program for
// Remove all leaf nodes from a N-ary Tree
type TreeNode struct {
    key int
    child [] *TreeNode
}
func getTreeNode(key int) * TreeNode {
    var me *TreeNode = &TreeNode {}
    // Set node key
    me.key = key
    // Create memory of TreeNode child
    me.child =  make([] *TreeNode,0) 
    return me
}
func(this *TreeNode) addChild(key int) {
    // Create a new node
    var node * TreeNode = getTreeNode(key)
    // Add node into child
    this.child = append(this.child, node)
}
type NAryTree struct {
    root * TreeNode
}
func getNAryTree() * NAryTree {
    var me *NAryTree = &NAryTree {}
    me.root = nil
    return me
}

func(this *NAryTree) deleteLeafNodes(node * TreeNode) {
    if node == nil {
        return
    }
    var i int = 0
    var temp * TreeNode = nil
    for (i < len(node.child)) {
        temp = node.child[i]
        if len(temp.child) == 0 {
            // When node is leaf node
            node.child = append(node.child[:i], node.child[i+1:]...)
        } else {
            this.deleteLeafNodes(temp)
            i++
        }
    }
}
func(this NAryTree) removeLeafNodes() {
    if this.root == nil {
        // When tree is empty
        return
    }
    if len(this.root.child) == 0 {
        // When delete root node
        this.root = nil
    } else {
        // Find and remove leaf nodes
        this.deleteLeafNodes(this.root)
    }
}
func(this NAryTree) printPreorder(node * TreeNode) {
    if node == nil {
        return
    }
    var i int = 0
    var temp * TreeNode = nil
    fmt.Print("  ", node.key)
    // iterating the child of given node
    for (i < len(node.child)) {
        temp = node.child[i]
        this.printPreorder(temp)
        i++
    }
}
func main() {
    var tree * NAryTree = getNAryTree()
    /*
               10
              /   \
             /     \
            /       \   
           8         5
          /|\      /|\ \ 
         / | \    / | \ \
        -2 1  6  7 18 3  4
          / \     \     /| \
         9  11    -1   2 1  3
           /  \
          17   12   
        -----------------------
        Constructing N-Ary tree
    */
    // First element of tree
    tree.root = getTreeNode(10)
    tree.root.addChild(8)
    tree.root.addChild(5)
    // Add child node [-2,1,6] in node (8)
    tree.root.child[0].addChild(-2)
    tree.root.child[0].addChild(1)
    tree.root.child[0].addChild(6)
    // Add child node [9,11] in node (1)
    tree.root.child[0].child[1].addChild(9)
    tree.root.child[0].child[1].addChild(11)
    // Add child node [17  12] in node (11)
    tree.root.child[0].child[1].child[1].addChild(17)
    tree.root.child[0].child[1].child[1].addChild(12)
    // Add child node [7 18 3  4] in node (5)
    tree.root.child[1].addChild(7)
    tree.root.child[1].addChild(18)
    tree.root.child[1].addChild(3)
    tree.root.child[1].addChild(4)
    // Add child node [-1] in node (7)
    tree.root.child[1].child[0].addChild(-1)
    // Add child node [2,1,3] in node (4)
    tree.root.child[1].child[3].addChild(2)
    tree.root.child[1].child[3].addChild(1)
    tree.root.child[1].child[3].addChild(3)
    fmt.Print("\n Before remove leaf nodes \n")
    tree.printPreorder(tree.root)
    // Remove leaf nodes
    tree.removeLeafNodes()
    fmt.Print("\n After remove leaf nodes \n")
    /*
           10                
          /  \
         /    \   
        /      \   
       8        5          
       |       / \ 
       |      /   \
       1     7     4       
        \            
        11          
                       
    */
    // After remove leaf nodes
    tree.printPreorder(tree.root)
}

Output

 Before remove leaf nodes
  10  8  -2  1  9  11  17  12  6  5  7  -1  18  3  4  2  1  3
 After remove leaf nodes
  10  8  1  11  5  7  4
// Include header file
#include <iostream>
#include <vector>

using namespace std;
// C++ program for
// Remove all leaf nodes from a N-ary Tree
class TreeNode
{
    public: int key;
    vector < TreeNode *> child;
    TreeNode(int key)
    {
        // Set node key
        this->key = key;

    }
    void addChild(int key)
    {
        // Create a new node
        TreeNode *node = new TreeNode(key);
        // Add node into child
        this->child.push_back(node);
    }
};
class NAryTree
{
    public: TreeNode *root;
    NAryTree()
    {
        this->root = NULL;
    }
    void deleteLeafNodes(TreeNode *node)
    {
        if (node == NULL)
        {
            return;
        }
        int i = 0;
        TreeNode *temp = NULL;
        while (i < node->child.size())
        {
            temp = node->child.at(i);
            if (temp->child.size() == 0)
            {
                // When node is leaf node
                 node->child.erase(node->child.begin() + i );
            }
            else
            {
                this->deleteLeafNodes(temp);
                i++;
            }
        }
    }
    void removeLeafNodes()
    {
        if (this->root == NULL)
        {
            // When tree is empty
            return;
        }
        if (this->root->child.size() == 0)
        {
            // When delete root node
            this->root = NULL;
        }
        else
        {
            // Find and remove leaf nodes
            this->deleteLeafNodes(this->root);
        }
    }
    void printPreorder(TreeNode *node)
    {
        if (node == NULL)
        {
            return;
        }
        int i = 0;
        TreeNode *temp = NULL;
        cout << "  " << node->key;
        // iterating the child of given node
        while (i < node->child.size())
        {
            temp = node->child.at(i);
            this->printPreorder(temp);
            i++;
        }
    }
};
int main()
{
    NAryTree *tree = new NAryTree();
    /*
               10
              /   \
             /     \
            /       \   
           8         5
          /|\      /|\ \ 
         / | \    / | \ \
        -2 1  6  7 18 3  4
          / \     \     /| \
         9  11    -1   2 1  3
           /  \
          17   12   
        -----------------------
        Constructing N-Ary tree
    */
    // First element of tree
    tree->root = new TreeNode(10);
    tree->root->addChild(8);
    tree->root->addChild(5);
    // Add child node [-2,1,6] in node (8)
    tree->root->child.at(0)->addChild(-2);
    tree->root->child.at(0)->addChild(1);
    tree->root->child.at(0)->addChild(6);
    // Add child node [9,11] in node (1)
    tree->root->child.at(0)->child.at(1)->addChild(9);
    tree->root->child.at(0)->child.at(1)->addChild(11);
    // Add child node [17  12] in node (11)
    tree->root->child.at(0)->child.at(1)->child.at(1)->addChild(17);
    tree->root->child.at(0)->child.at(1)->child.at(1)->addChild(12);
    // Add child node [7 18 3  4] in node (5)
    tree->root->child.at(1)->addChild(7);
    tree->root->child.at(1)->addChild(18);
    tree->root->child.at(1)->addChild(3);
    tree->root->child.at(1)->addChild(4);
    // Add child node [-1] in node (7)
    tree->root->child.at(1)->child.at(0)->addChild(-1);
    // Add child node [2,1,3] in node (4)
    tree->root->child.at(1)->child.at(3)->addChild(2);
    tree->root->child.at(1)->child.at(3)->addChild(1);
    tree->root->child.at(1)->child.at(3)->addChild(3);
    cout << "\n Before remove leaf nodes \n";
    tree->printPreorder(tree->root);
    // Remove leaf nodes
    tree->removeLeafNodes();
    cout << "\n After remove leaf nodes \n";
    /*
           10                
          /  \
         /    \   
        /      \   
       8        5          
       |       / \ 
       |      /   \
       1     7     4       
        \            
        11          
                       
    */
    // After remove leaf nodes
    tree->printPreorder(tree->root);
    return 0;
}

Output

 Before remove leaf nodes
  10  8  -2  1  9  11  17  12  6  5  7  -1  18  3  4  2  1  3
 After remove leaf nodes
  10  8  1  11  5  7  4
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Remove all leaf nodes from a N-ary Tree
public class TreeNode
{
    public int key;
    public List < TreeNode > child;
    public TreeNode(int key)
    {
        // Set node key
        this.key = key;
        // Create memory of TreeNode child
        this.child = new List < TreeNode > ();
    }
    public void addChild(int key)
    {
        // Create a new node
        TreeNode node = new TreeNode(key);
        // Add node into child
        this.child.Add(node);
    }
}
public class NAryTree
{
    public TreeNode root;
    public NAryTree()
    {
        this.root = null;
    }
    public void deleteLeafNodes(TreeNode node)
    {
        if (node == null)
        {
            return;
        }
        int i = 0;
        TreeNode temp = null;
        while (i < node.child.Count)
        {
            temp = node.child[i];
            if (temp.child.Count == 0)
            {
                // When node is leaf node
                node.child.RemoveAt(i);
            }
            else
            {
                this.deleteLeafNodes(temp);
                i++;
            }
        }
    }
    public void removeLeafNodes()
    {
        if (this.root == null)
        {
            // When tree is empty
            return;
        }
        if (this.root.child.Count == 0)
        {
            // When delete root node
            this.root = null;
        }
        else
        {
            // Find and remove leaf nodes
            this.deleteLeafNodes(this.root);
        }
    }
    public void printPreorder(TreeNode node)
    {
        if (node == null)
        {
            return;
        }
        int i = 0;
        TreeNode temp = null;
        Console.Write("  " + node.key);
        // iterating the child of given node
        while (i < node.child.Count)
        {
            temp = node.child[i];
            this.printPreorder(temp);
            i++;
        }
    }
    public static void Main(String[] args)
    {
        NAryTree tree = new NAryTree();
        /*
                   10
                  /   \
                 /     \
                /       \   
               8         5
              /|\      /|\ \ 
             / | \    / | \ \
            -2 1  6  7 18 3  4
              / \     \     /| \
             9  11    -1   2 1  3
               /  \
              17   12   
            -----------------------
            Constructing N-Ary tree
        */
        // First element of tree
        tree.root = new TreeNode(10);
        tree.root.addChild(8);
        tree.root.addChild(5);
        // Add child node [-2,1,6] in node (8)
        tree.root.child[0].addChild(-2);
        tree.root.child[0].addChild(1);
        tree.root.child[0].addChild(6);
        // Add child node [9,11] in node (1)
        tree.root.child[0].child[1].addChild(9);
        tree.root.child[0].child[1].addChild(11);
        // Add child node [17  12] in node (11)
        tree.root.child[0].child[1].child[1].addChild(17);
        tree.root.child[0].child[1].child[1].addChild(12);
        // Add child node [7 18 3  4] in node (5)
        tree.root.child[1].addChild(7);
        tree.root.child[1].addChild(18);
        tree.root.child[1].addChild(3);
        tree.root.child[1].addChild(4);
        // Add child node [-1] in node (7)
        tree.root.child[1].child[0].addChild(-1);
        // Add child node [2,1,3] in node (4)
        tree.root.child[1].child[3].addChild(2);
        tree.root.child[1].child[3].addChild(1);
        tree.root.child[1].child[3].addChild(3);
        Console.Write("\n Before remove leaf nodes \n");
        tree.printPreorder(tree.root);
        // Remove leaf nodes
        tree.removeLeafNodes();
        Console.Write("\n After remove leaf nodes \n");
        /*
               10                
              /  \
             /    \   
            /      \   
           8        5          
           |       / \ 
           |      /   \
           1     7     4       
            \            
            11          
                           
        */
        // After remove leaf nodes
        tree.printPreorder(tree.root);
    }
}

Output

 Before remove leaf nodes
  10  8  -2  1  9  11  17  12  6  5  7  -1  18  3  4  2  1  3
 After remove leaf nodes
  10  8  1  11  5  7  4
<?php
// Php program for
// Remove all leaf nodes from a N-ary Tree
class TreeNode
{
    public $key;
    public $child;
    public  function __construct($key)
    {
        // Set node key
        $this->key = $key;
        // Create memory of TreeNode child
        $this->child = array();
    }
    public  function addChild($key)
    {
        // Create a new node
        $node = new TreeNode($key);
        // Add node into child
        $this->child[] = $node;
    }
}
class NAryTree
{
    public $root;
    public  function __construct()
    {
        $this->root = NULL;
    }
    public  function deleteLeafNodes($node)
    {
        if ($node == NULL)
        {
            return;
        }
        $i = 0;
        $temp = NULL;
        while ($i < count($node->child))
        {
            $temp = $node->child[$i];
            if (count($temp->child) == 0)
            {
                // When node is leaf node
                unset($node->child[$i]);
                // Reset key value
                $node->child = array_merge($node->child); 
            }
            else
            {
                $this->deleteLeafNodes($temp);
                $i++;
            }
        }
    }
    public  function removeLeafNodes()
    {
        if ($this->root == NULL)
        {
            // When tree is empty
            return;
        }
        if (count($this->root->child) == 0)
        {
            // When delete root node
            $this->root = NULL;
        }
        else
        {
            // Find and remove leaf nodes
            $this->deleteLeafNodes($this->root);
        }
    }
    public  function printPreorder($node)
    {
        if ($node == NULL)
        {
            return;
        }
        $i = 0;
        $temp = NULL;
        echo("  ".$node->key);
        // iterating the child of given node
        while ($i < count($node->child))
        {
            $temp = $node->child[$i];
            $this->printPreorder($temp);
            $i++;
        }
    }
}

function main()
{
    $tree = new NAryTree();
    /*
               10
              /   \
             /     \
            /       \   
           8         5
          /|\      /|\ \ 
         / | \    / | \ \
        -2 1  6  7 18 3  4
          / \     \     /| \
         9  11    -1   2 1  3
           /  \
          17   12   
        -----------------------
        Constructing N-Ary tree
    */
    // First element of tree
    $tree->root = new TreeNode(10);
    $tree->root->addChild(8);
    $tree->root->addChild(5);
    // Add child node [-2,1,6] in node (8)
    $tree->root->child[0]->addChild(-2);
    $tree->root->child[0]->addChild(1);
    $tree->root->child[0]->addChild(6);
    // Add child node [9,11] in node (1)
    $tree->root->child[0]->child[1]->addChild(9);
    $tree->root->child[0]->child[1]->addChild(11);
    // Add child node [17  12] in node (11)
    $tree->root->child[0]->child[1]->child[1]->addChild(17);
    $tree->root->child[0]->child[1]->child[1]->addChild(12);
    // Add child node [7 18 3  4] in node (5)
    $tree->root->child[1]->addChild(7);
    $tree->root->child[1]->addChild(18);
    $tree->root->child[1]->addChild(3);
    $tree->root->child[1]->addChild(4);
    // Add child node [-1] in node (7)
    $tree->root->child[1]->child[0]->addChild(-1);
    // Add child node [2,1,3] in node (4)
    $tree->root->child[1]->child[3]->addChild(2);
    $tree->root->child[1]->child[3]->addChild(1);
    $tree->root->child[1]->child[3]->addChild(3);
    echo("\n Before remove leaf nodes \n");
    $tree->printPreorder($tree->root);
    // Remove leaf nodes
    $tree->removeLeafNodes();
    echo("\n After remove leaf nodes \n");
    /*
           10                
          /  \
         /    \   
        /      \   
       8        5          
       |       / \ 
       |      /   \
       1     7     4       
        \            
        11          
                       
    */
    // After remove leaf nodes
    $tree->printPreorder($tree->root);
}
main();

Output

 Before remove leaf nodes
  10  8  -2  1  9  11  17  12  6  5  7  -1  18  3  4  2  1  3
 After remove leaf nodes
  10  8  1  11  5  7  4
// Node JS program for
// Remove all leaf nodes from a N-ary Tree
class TreeNode
{
    constructor(key)
    {
        // Set node key
        this.key = key;
        // Create memory of TreeNode child
        this.child = [];
    }
    addChild(key)
    {
        // Create a new node
        var node = new TreeNode(key);
        // Add node into child
        this.child.push(node);
    }
}
class NAryTree
{
    constructor()
    {
        this.root = null;
    }
    deleteLeafNodes(node)
    {
        if (node == null)
        {
            return;
        }
        var i = 0;
        var temp = null;
        while (i < node.child.length)
        {
            temp = node.child[i];
            if (temp.child.length == 0)
            {
                // When node is leaf node
                node.child.splice(i,i+1);
            }
            else
            {
                this.deleteLeafNodes(temp);
                i++;
            }
        }
    }
    removeLeafNodes()
    {
        if (this.root == null)
        {
            // When tree is empty
            return;
        }
        if (this.root.child.length == 0)
        {
            // When delete root node
            this.root = null;
        }
        else
        {
            // Find and remove leaf nodes
            this.deleteLeafNodes(this.root);
        }
    }
    printPreorder(node)
    {
        if (node == null)
        {
            return;
        }
        var i = 0;
        var temp = null;
        process.stdout.write("  " + node.key);
        // iterating the child of given node
        while (i < node.child.length)
        {
            temp = node.child[i];
            this.printPreorder(temp);
            i++;
        }
    }
}

function main()
{
    var tree = new NAryTree();
    /*
               10
              /   \
             /     \
            /       \   
           8         5
          /|\      /|\ \ 
         / | \    / | \ \
        -2 1  6  7 18 3  4
          / \     \     /| \
         9  11    -1   2 1  3
           /  \
          17   12   
        -----------------------
        Constructing N-Ary tree
    */
    // First element of tree
    tree.root = new TreeNode(10);
    tree.root.addChild(8);
    tree.root.addChild(5);
    // Add child node [-2,1,6] in node (8)
    tree.root.child[0].addChild(-2);
    tree.root.child[0].addChild(1);
    tree.root.child[0].addChild(6);
    // Add child node [9,11] in node (1)
    tree.root.child[0].child[1].addChild(9);
    tree.root.child[0].child[1].addChild(11);
    // Add child node [17  12] in node (11)
    tree.root.child[0].child[1].child[1].addChild(17);
    tree.root.child[0].child[1].child[1].addChild(12);
    // Add child node [7 18 3  4] in node (5)
    tree.root.child[1].addChild(7);
    tree.root.child[1].addChild(18);
    tree.root.child[1].addChild(3);
    tree.root.child[1].addChild(4);
    // Add child node [-1] in node (7)
    tree.root.child[1].child[0].addChild(-1);
    // Add child node [2,1,3] in node (4)
    tree.root.child[1].child[3].addChild(2);
    tree.root.child[1].child[3].addChild(1);
    tree.root.child[1].child[3].addChild(3);
    process.stdout.write("\n Before remove leaf nodes \n");
    tree.printPreorder(tree.root);
    // Remove leaf nodes
    tree.removeLeafNodes();
    process.stdout.write("\n After remove leaf nodes \n");
    /*
           10                
          /  \
         /    \   
        /      \   
       8        5          
       |       / \ 
       |      /   \
       1     7     4       
        \            
        11          
                       
    */
    // After remove leaf nodes
    tree.printPreorder(tree.root);
}
main();

Output

 Before remove leaf nodes
  10  8  -2  1  9  11  17  12  6  5  7  -1  18  3  4  2  1  3
 After remove leaf nodes
  10  8  1  11  5  7  4
#  Python 3 program for
#  Remove all leaf nodes from a N-ary Tree
class TreeNode :
    def __init__(self, key) :
        #  Set node key
        self.key = key
        #  Create memory of TreeNode child
        self.child = []
    
    def addChild(self, key) :
        #  Create a new node
        node = TreeNode(key)
        #  Add node into child
        self.child.append(node)
    

class NAryTree :
    def __init__(self) :
        self.root = None
    
    def deleteLeafNodes(self, node) :
        if (node == None) :
            return
        
        i = 0
        temp = None
        while (i < len(node.child)) :
            temp = node.child[i]
            if (len(temp.child) == 0) :
                #  When node is leaf node
                del node.child[i]
            else :
                self.deleteLeafNodes(temp)
                i += 1
            
        
    
    def removeLeafNodes(self) :
        if (self.root == None) :
            #  When tree is empty
            return
        
        if (len(self.root.child) == 0) :
            #  When delete root node
            self.root = None
        else :
            #  Find and remove leaf nodes
            self.deleteLeafNodes(self.root)
        
    
    def printPreorder(self, node) :
        if (node == None) :
            return
        
        i = 0
        temp = None
        print(" ", node.key, end = "")
        #  iterating the child of given node
        while (i < len(node.child)) :
            temp = node.child[i]
            self.printPreorder(temp)
            i += 1
        
    

def main() :
    tree = NAryTree()
    #           10
    #          /   \
    #         /     \
    #        /       \   
    #       8         5
    #      /|\      /|\ \ 
    #     / | \    / | \ \
    #    -2 1  6  7 18 3  4
    #      / \     \     /| \
    #     9  11    -1   2 1  3
    #       /  \
    #      17   12   
    #    -----------------------
    #    Constructing N-Ary tree
    #  First element of tree
    tree.root = TreeNode(10)
    tree.root.addChild(8)
    tree.root.addChild(5)
    #  Add child node [-2,1,6] in node (8)
    tree.root.child[0].addChild(-2)
    tree.root.child[0].addChild(1)
    tree.root.child[0].addChild(6)
    #  Add child node [9,11] in node (1)
    tree.root.child[0].child[1].addChild(9)
    tree.root.child[0].child[1].addChild(11)
    #  Add child node [17  12] in node (11)
    tree.root.child[0].child[1].child[1].addChild(17)
    tree.root.child[0].child[1].child[1].addChild(12)
    #  Add child node [7 18 3  4] in node (5)
    tree.root.child[1].addChild(7)
    tree.root.child[1].addChild(18)
    tree.root.child[1].addChild(3)
    tree.root.child[1].addChild(4)
    #  Add child node [-1] in node (7)
    tree.root.child[1].child[0].addChild(-1)
    #  Add child node [2,1,3] in node (4)
    tree.root.child[1].child[3].addChild(2)
    tree.root.child[1].child[3].addChild(1)
    tree.root.child[1].child[3].addChild(3)
    print("\n Before remove leaf nodes ")
    tree.printPreorder(tree.root)
    #  Remove leaf nodes
    tree.removeLeafNodes()
    print("\n After remove leaf nodes ")
    #       10                
    #      /  \
    #     /    \   
    #    /      \   
    #   8        5          
    #   |       / \ 
    #   |      /   \
    #   1     7     4       
    #    \            
    #    11          
    #  After remove leaf nodes
    tree.printPreorder(tree.root)

if __name__ == "__main__": main()

Output

 Before remove leaf nodes
  10  8  -2  1  9  11  17  12  6  5  7  -1  18  3  4  2  1  3
 After remove leaf nodes
  10  8  1  11  5  7  4
#  Ruby program for
#  Remove all leaf nodes from a N-ary Tree
class TreeNode 
    # Define the accessor and reader of class TreeNode
    attr_reader :key, :child
    attr_accessor :key, :child
    def initialize(key) 
        #  Set node key
        self.key = key
        #  Create memory of TreeNode child
        self.child = []
    end

    def addChild(key) 
        #  Create a new node
        node = TreeNode.new(key)
        #  Add node into child
        self.child.push(node)
    end

end

class NAryTree 
    # Define the accessor and reader of class NAryTree
    attr_reader :root
    attr_accessor :root
    def initialize() 
        self.root = nil
    end

    def deleteLeafNodes(node) 
        if (node == nil) 
            return
        end

        i = 0
        temp = nil
        while (i < node.child.length) 
            temp = node.child[i]
            if (temp.child.length == 0) 
                #  When node is leaf node
                node.child.delete_at(i)
            else
                self.deleteLeafNodes(temp)
                i += 1
            end

        end

    end

    def removeLeafNodes() 
        if (self.root == nil) 
            #  When tree is empty
            return
        end

        if (self.root.child.length == 0) 
            #  When delete root node
            self.root = nil
        else
 
            #  Find and remove leaf nodes
            self.deleteLeafNodes(self.root)
        end

    end

    def printPreorder(node) 
        if (node == nil) 
            return
        end

        i = 0
        temp = nil
        print("  ", node.key)
        #  iterating the child of given node
        while (i < node.child.length) 
            temp = node.child[i]
            self.printPreorder(temp)
            i += 1
        end

    end

end

def main() 
    tree = NAryTree.new()
    #           10
    #          /   \
    #         /     \
    #        /       \   
    #       8         5
    #      /|\      /|\ \ 
    #     / | \    / | \ \
    #    -2 1  6  7 18 3  4
    #      / \     \     /| \
    #     9  11    -1   2 1  3
    #       /  \
    #      17   12   
    #    -----------------------
    #    Constructing N-Ary tree
    #  First element of tree
    tree.root = TreeNode.new(10)
    tree.root.addChild(8)
    tree.root.addChild(5)
    #  Add child node [-2,1,6] in node (8)
    tree.root.child[0].addChild(-2)
    tree.root.child[0].addChild(1)
    tree.root.child[0].addChild(6)
    #  Add child node [9,11] in node (1)
    tree.root.child[0].child[1].addChild(9)
    tree.root.child[0].child[1].addChild(11)
    #  Add child node [17  12] in node (11)
    tree.root.child[0].child[1].child[1].addChild(17)
    tree.root.child[0].child[1].child[1].addChild(12)
    #  Add child node [7 18 3  4] in node (5)
    tree.root.child[1].addChild(7)
    tree.root.child[1].addChild(18)
    tree.root.child[1].addChild(3)
    tree.root.child[1].addChild(4)
    #  Add child node [-1] in node (7)
    tree.root.child[1].child[0].addChild(-1)
    #  Add child node [2,1,3] in node (4)
    tree.root.child[1].child[3].addChild(2)
    tree.root.child[1].child[3].addChild(1)
    tree.root.child[1].child[3].addChild(3)
    print("\n Before remove leaf nodes \n")
    tree.printPreorder(tree.root)
    #  Remove leaf nodes
    tree.removeLeafNodes()
    print("\n After remove leaf nodes \n")
    #       10                
    #      /  \
    #     /    \   
    #    /      \   
    #   8        5          
    #   |       / \ 
    #   |      /   \
    #   1     7     4       
    #    \            
    #    11          
    #  After remove leaf nodes
    tree.printPreorder(tree.root)
end

main()

Output

 Before remove leaf nodes 
  10  8  -2  1  9  11  17  12  6  5  7  -1  18  3  4  2  1  3
 After remove leaf nodes 
  10  8  1  11  5  7  4
import scala.collection.mutable._;
// Scala program for
// Remove all leaf nodes from a N-ary Tree
class TreeNode(var key: Int,
    var child: ArrayBuffer[TreeNode])
{
    def this(key: Int)
    {
        // Set node key
        // Create memory of TreeNode child
        this(key, new ArrayBuffer[TreeNode]());
    }
    def addChild(key: Int): Unit = {
        // Create a new node
        var node: TreeNode = new TreeNode(key);
        // Add node into child
        this.child += node;
    }
}
class NAryTree(var root: TreeNode)
{
    def this()
    {
        this(null);
    }
    def deleteLeafNodes(node: TreeNode): Unit = {
        if (node == null)
        {
            return;
        }
        var i: Int = 0;
        var temp: TreeNode = null;
        while (i < node.child.size)
        {
            temp = node.child(i);
            if (temp.child.size == 0)
            {
                // When node is leaf node
                node.child.remove(i);
            }
            else
            {
                deleteLeafNodes(temp);
                i += 1;
            }
        }
    }
    def removeLeafNodes(): Unit = {
        if (this.root == null)
        {
            // When tree is empty
            return;
        }
        if (this.root.child.size == 0)
        {
            // When delete root node
            this.root = null;
        }
        else
        {
            // Find and remove leaf nodes
            this.deleteLeafNodes(this.root);
        }
    }
    def printPreorder(node: TreeNode): Unit = {
        if (node == null)
        {
            return;
        }
        var i: Int = 0;
        var temp: TreeNode = null;
        print("  " + node.key);
        // iterating the child of given node
        while (i < node.child.size)
        {
            temp = node.child(i);
            printPreorder(temp);
            i += 1;
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var tree: NAryTree = new NAryTree();
        /*
                   10
                  /   \
                 /     \
                /       \   
               8         5
              /|\      /|\ \ 
             / | \    / | \ \
            -2 1  6  7 18 3  4
              / \     \     /| \
             9  11    -1   2 1  3
               /  \
              17   12   
            -----------------------
            Constructing N-Ary tree
        */
        // First element of tree
        tree.root = new TreeNode(10);
        tree.root.addChild(8);
        tree.root.addChild(5);
        // Add child node [-2,1,6] in node (8)
        tree.root.child(0).addChild(-2);
        tree.root.child(0).addChild(1);
        tree.root.child(0).addChild(6);
        // Add child node [9,11] in node (1)
        tree.root.child(0).child(1).addChild(9);
        tree.root.child(0).child(1).addChild(11);
        // Add child node [17  12] in node (11)
        tree.root.child(0).child(1).child(1).addChild(17);
        tree.root.child(0).child(1).child(1).addChild(12);
        // Add child node [7 18 3  4] in node (5)
        tree.root.child(1).addChild(7);
        tree.root.child(1).addChild(18);
        tree.root.child(1).addChild(3);
        tree.root.child(1).addChild(4);
        // Add child node [-1] in node (7)
        tree.root.child(1).child(0).addChild(-1);
        // Add child node [2,1,3] in node (4)
        tree.root.child(1).child(3).addChild(2);
        tree.root.child(1).child(3).addChild(1);
        tree.root.child(1).child(3).addChild(3);
        print("\n Before remove leaf nodes \n");
        tree.printPreorder(tree.root);
        // Remove leaf nodes
        tree.removeLeafNodes();
        print("\n After remove leaf nodes \n");
        /*
               10                
              /  \
             /    \   
            /      \   
           8        5          
           |       / \ 
           |      /   \
           1     7     4       
            \            
            11          
                           
        */
        // After remove leaf nodes
        tree.printPreorder(tree.root);
    }
}

Output

 Before remove leaf nodes
  10  8  -2  1  9  11  17  12  6  5  7  -1  18  3  4  2  1  3
 After remove leaf nodes
  10  8  1  11  5  7  4
import Foundation;
// Swift 4 program for
// Remove all leaf nodes from a N-ary Tree
class TreeNode
{
    var key: Int;
    var child: [TreeNode? ];
    init(_ key: Int)
    {
        // Set node key
        self.key = key;
        // Create memory of TreeNode child
        self.child = [TreeNode? ]();
    }
    func addChild(_ key: Int)
    {
        // Create a new node
        let node: TreeNode = TreeNode(key);
        // Add node into child
        self.child.append(node);
    }
}
class NAryTree
{
    var root: TreeNode? ;
    init()
    {
        self.root = nil;
    }
    func deleteLeafNodes(_ node: TreeNode? )
    {
        if (node == nil)
        {
            return;
        }
        var i: Int = 0;
        var temp: TreeNode? = nil;
        while (i < node!.child.count)
        {
            temp = node!.child[i];
            if (temp!.child.count == 0)
            {
                // When node is leaf node
                node!.child.remove(at:i);
            }
            else
            {
                self.deleteLeafNodes(temp);
                i += 1;
            }
        }
    }
    func removeLeafNodes()
    {
        if (self.root == nil)
        {
            // When tree is empty
            return;
        }
        if (self.root!.child.count == 0)
        {
            // When delete root node
            self.root = nil;
        }
        else
        {
            // Find and remove leaf nodes
            self.deleteLeafNodes(self.root);
        }
    }
    func printPreorder(_ node: TreeNode? )
    {
        if (node == nil)
        {
            return;
        }
        var i: Int = 0;
        var temp: TreeNode? = nil;
        print("  ", node!.key, terminator: "");
        // iterating the child of given node
        while (i < node!.child.count)
        {
            temp = node!.child[i];
            self.printPreorder(temp);
            i += 1;
        }
    }
}
func main()
{
    let tree: NAryTree = NAryTree();
    /*
               10
              /   \
             /     \
            /       \   
           8         5
          /|\      /|\ \ 
         / | \    / | \ \
        -2 1  6  7 18 3  4
          / \     \     /| \
         9  11    -1   2 1  3
           /  \
          17   12   
        -----------------------
        Constructing N-Ary tree
    */
    // First element of tree
    tree.root = TreeNode(10);
    tree.root!.addChild(8);
    tree.root!.addChild(5);
    // Add child node [-2,1,6] in node (8)
    tree.root!.child[0]!.addChild(-2);
    tree.root!.child[0]!.addChild(1);
    tree.root!.child[0]!.addChild(6);
    // Add child node [9,11] in node (1)
    tree.root!.child[0]!.child[1]!.addChild(9);
    tree.root!.child[0]!.child[1]!.addChild(11);
    // Add child node [17  12] in node (11)
    tree.root!.child[0]!.child[1]!.child[1]!.addChild(17);
    tree.root!.child[0]!.child[1]!.child[1]!.addChild(12);
    // Add child node [7 18 3  4] in node (5)
    tree.root!.child[1]!.addChild(7);
    tree.root!.child[1]!.addChild(18);
    tree.root!.child[1]!.addChild(3);
    tree.root!.child[1]!.addChild(4);
    // Add child node [-1] in node (7)
    tree.root!.child[1]!.child[0]!.addChild(-1);
    // Add child node [2,1,3] in node (4)
    tree.root!.child[1]!.child[3]!.addChild(2);
    tree.root!.child[1]!.child[3]!.addChild(1);
    tree.root!.child[1]!.child[3]!.addChild(3);
    print("\n Before remove leaf nodes ");
    tree.printPreorder(tree.root);
    // Remove leaf nodes
    tree.removeLeafNodes();
    print("\n After remove leaf nodes ");
    /*
           10                
          /  \
         /    \   
        /      \   
       8        5          
       |       / \ 
       |      /   \
       1     7     4       
        \            
        11          
                       
    */
    // After remove leaf nodes
    tree.printPreorder(tree.root);
}
main();

Output

 Before remove leaf nodes
   10   8   -2   1   9   11   17   12   6   5   7   -1   18   3   4   2   1   3
 After remove leaf nodes
   10   8   1   11   5   7   4
// Kotlin program for
// Remove all leaf nodes from a N-ary Tree
class TreeNode
{
    var key: Int;
    var child: MutableList < TreeNode >;
    constructor(key: Int)
    {
        // Set node key
        this.key = key;
        // Create memory of TreeNode child
        this.child = mutableListOf < TreeNode > ();
    }
    fun addChild(key: Int): Unit
    {
        // Create a new node
        val node: TreeNode = TreeNode(key);
        // Add node into child
        this.child.add(node);
    }
}
class NAryTree
{
    var root: TreeNode ? ;
    constructor()
    {
        this.root = null;
    }
    fun deleteLeafNodes(node: TreeNode ? ): Unit
    {
        if (node == null)
        {
            return;
        }
        var i: Int = 0;
        var temp: TreeNode ? ;
        while (i < node.child.size)
        {
            temp = node.child[i];
            if (temp.child.size == 0)
            {
                // When node is leaf node
                node.child.removeAt(i);
            }
            else
            {
                this.deleteLeafNodes(temp);
                i += 1;
            }
        }
    }
    fun removeLeafNodes(): Unit
    {
        if (this.root == null)
        {
            // When tree is empty
            return;
        }
        if (this.root!!.child.size == 0)
        {
            // When delete root node
            this.root = null;
        }
        else
        {
            // Find and remove leaf nodes
            this.deleteLeafNodes(this.root);
        }
    }
    fun printPreorder(node: TreeNode ? ): Unit
    {
        if (node == null)
        {
            return;
        }
        var i: Int = 0;
        var temp: TreeNode ? ;
        print("  " + node.key);
        // iterating the child of given node
        while (i < node.child.size)
        {
            temp = node.child[i];
            this.printPreorder(temp);
            i += 1;
        }
    }
}
fun main(args: Array < String > ): Unit
{
    val tree: NAryTree = NAryTree();
    /*
               10
              /   \
             /     \
            /       \   
           8         5
          /|\      /|\ \ 
         / | \    / | \ \
        -2 1  6  7 18 3  4
          / \     \     /| \
         9  11    -1   2 1  3
           /  \
          17   12   
        -----------------------
        Constructing N-Ary tree
    */
    // First element of tree
    tree.root = TreeNode(10);
    tree.root?.addChild(8);
    tree.root?.addChild(5);
    // Add child node [-2,1,6] in node (8)
    tree.root!!.child[0].addChild(-2);
    tree.root!!.child[0].addChild(1);
    tree.root!!.child[0].addChild(6);
    // Add child node [9,11] in node (1)
    tree.root!!.child[0].child[1].addChild(9);
    tree.root!!.child[0].child[1].addChild(11);
    // Add child node [17  12] in node (11)
    tree.root!!.child[0].child[1].child[1].addChild(17);
    tree.root!!.child[0].child[1].child[1].addChild(12);
    // Add child node [7 18 3  4] in node (5)
    tree.root!!.child[1].addChild(7);
    tree.root!!.child[1].addChild(18);
    tree.root!!.child[1].addChild(3);
    tree.root!!.child[1].addChild(4);
    // Add child node [-1] in node (7)
    tree.root!!.child[1].child[0].addChild(-1);
    // Add child node [2,1,3] in node (4)
    tree.root!!.child[1].child[3].addChild(2);
    tree.root!!.child[1].child[3].addChild(1);
    tree.root!!.child[1].child[3].addChild(3);
    print("\n Before remove leaf nodes \n");
    tree.printPreorder(tree.root);
    // Remove leaf nodes
    tree.removeLeafNodes();
    print("\n After remove leaf nodes \n");
    /*
           10                
          /  \
         /    \   
        /      \   
       8        5          
       |       / \ 
       |      /   \
       1     7     4       
        \            
        11          
                       
    */
    // After remove leaf nodes
    tree.printPreorder(tree.root);
}

Output

 Before remove leaf nodes
  10  8  -2  1  9  11  17  12  6  5  7  -1  18  3  4  2  1  3
 After remove leaf nodes
  10  8  1  11  5  7  4


Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment







© 2021, kalkicode.com, All rights reserved