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.
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 4package 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 4import 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 4import 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