Replace every node with depth in n-ary tree
Here given code implementation process.
import java.util.Vector;
import java.util.ArrayList;
// Java program for
// Replace every node with depth in n-ary tree
class TreeNode
{
public int key;
public Vector < TreeNode > child;
public TreeNode(int key)
{
this.key = key;
this.child = new Vector < TreeNode > ();
}
public void addChild(int key)
{
TreeNode t = new TreeNode(key);
this.child.add(t);
}
}
public class NAryTree
{
public TreeNode root;
public NAryTree()
{
// Set initial tree root to null
this.root = null;
}
public void replaceByDepth(TreeNode node, int depth)
{
int i = 0;
// Update node value by depth
node.key = depth;
// iterating the child of given node
while (i < node.child.size())
{
// Recursively visit child node
replaceByDepth(node.child.get(i), depth + 1);
i++;
}
}
// Display preorder traversal of binary tree
public void printPreorder(TreeNode node)
{
if (node == null)
{
return;
}
int i = 0;
TreeNode temp = null;
// Display node value
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 2 1 3
/ \ |
17 12 20
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = new TreeNode(10);
tree.root.addChild(8);
tree.root.addChild(5);
// Add child node [-2,1,5] 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 [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);
// Add child node [20] in node (2)
tree.root.child.get(1).child.get(3).child.get(0).addChild(20);
// Before update
System.out.print("\n Before replace \n");
tree.printPreorder(tree.root);
// Change node value
tree.replaceByDepth(tree.root, 0);
// After update
System.out.print("\n After replace by depth \n");
tree.printPreorder(tree.root);
}
}
input
Before replace
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 20 1 3
After replace by depth
0 1 2 2 3 3 4 4 2 1 2 2 2 2 3 4 3 3
// Include header file
#include <iostream>
#include <vector>
using namespace std;
// C++ program for
// Replace every node with depth in n-ary tree
class TreeNode
{
public: int key;
vector < TreeNode *> child;
TreeNode(int key)
{
this->key = key;
}
void addChild(int key)
{
TreeNode *t = new TreeNode(key);
this->child.push_back(t);
}
};
class NAryTree
{
public: TreeNode *root;
NAryTree()
{
this->root = NULL;
}
void replaceByDepth(TreeNode *node, int depth)
{
int i = 0;
// Update node value by depth
node->key = depth;
// iterating the child of given node
while (i < node->child.size())
{
// Recursively visit child node
this->replaceByDepth(node->child.at(i), depth + 1);
i++;
}
}
// Display preorder traversal of binary tree
void printPreorder(TreeNode *node)
{
if (node == NULL)
{
return;
}
int i = 0;
TreeNode *temp = NULL;
// Display node value
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 2 1 3
/ \ |
17 12 20
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree->root = new TreeNode(10);
tree->root->addChild(8);
tree->root->addChild(5);
// Add child node [-2,1,5] 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 [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);
// Add child node [20] in node (2)
tree->root->child.at(1)->child.at(3)->child.at(0)->addChild(20);
// Before update
cout << "\n Before replace \n";
tree->printPreorder(tree->root);
// Change node value
tree->replaceByDepth(tree->root, 0);
// After update
cout << "\n After replace by depth \n";
tree->printPreorder(tree->root);
return 0;
}
input
Before replace
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 20 1 3
After replace by depth
0 1 2 2 3 3 4 4 2 1 2 2 2 2 3 4 3 3
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Replace every node with depth in n-ary tree
public class TreeNode
{
public int key;
public List < TreeNode > child;
public TreeNode(int key)
{
this.key = key;
this.child = new List < TreeNode > ();
}
public void addChild(int key)
{
TreeNode t = new TreeNode(key);
this.child.Add(t);
}
}
public class NAryTree
{
public TreeNode root;
public NAryTree()
{
// Set initial tree root to null
this.root = null;
}
public void replaceByDepth(TreeNode node, int depth)
{
int i = 0;
// Update node value by depth
node.key = depth;
// iterating the child of given node
while (i < node.child.Count)
{
// Recursively visit child node
this.replaceByDepth(node.child[i], depth + 1);
i++;
}
}
// Display preorder traversal of binary tree
public void printPreorder(TreeNode node)
{
if (node == null)
{
return;
}
int i = 0;
TreeNode temp = null;
// Display node value
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 2 1 3
/ \ |
17 12 20
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = new TreeNode(10);
tree.root.addChild(8);
tree.root.addChild(5);
// Add child node [-2,1,5] 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 [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);
// Add child node [20] in node (2)
tree.root.child[1].child[3].child[0].addChild(20);
// Before update
Console.Write("\n Before replace \n");
tree.printPreorder(tree.root);
// Change node value
tree.replaceByDepth(tree.root, 0);
// After update
Console.Write("\n After replace by depth \n");
tree.printPreorder(tree.root);
}
}
input
Before replace
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 20 1 3
After replace by depth
0 1 2 2 3 3 4 4 2 1 2 2 2 2 3 4 3 3
<?php
// Php program for
// Replace every node with depth in n-ary tree
class TreeNode
{
public $key;
public $child;
public function __construct($key)
{
$this->key = $key;
$this->child = array();
}
public function addChild($key)
{
$t = new TreeNode($key);
$this->child[] = $t;
}
}
class NAryTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
public function replaceByDepth($node, $depth)
{
$i = 0;
// Update node value by depth
$node->key = $depth;
// iterating the child of given node
while ($i < count($node->child))
{
// Recursively visit child node
$this->replaceByDepth($node->child[$i], $depth + 1);
$i++;
}
}
// Display preorder traversal of binary tree
public function printPreorder($node)
{
if ($node == NULL)
{
return;
}
$i = 0;
$temp = NULL;
// Display node value
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 2 1 3
/ \ |
17 12 20
-----------------------
Constructing N-Arr tree
*/
// First element of tree
$tree->root = new TreeNode(10);
$tree->root->addChild(8);
$tree->root->addChild(5);
// Add child node [-2,1,5] 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 [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);
// Add child node [20] in node (2)
$tree->root->child[1]->child[3]->child[0]->addChild(20);
// Before update
echo("\n Before replace \n");
$tree->printPreorder($tree->root);
// Change node value
$tree->replaceByDepth($tree->root, 0);
// After update
echo("\n After replace by depth \n");
$tree->printPreorder($tree->root);
}
main();
input
Before replace
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 20 1 3
After replace by depth
0 1 2 2 3 3 4 4 2 1 2 2 2 2 3 4 3 3
// Node JS program for
// Replace every node with depth in n-ary tree
class TreeNode
{
constructor(key)
{
this.key = key;
this.child = [];
}
addChild(key)
{
var t = new TreeNode(key);
this.child.push(t);
}
}
class NAryTree
{
constructor()
{
this.root = null;
}
replaceByDepth(node, depth)
{
var i = 0;
// Update node value by depth
node.key = depth;
// iterating the child of given node
while (i < node.child.length)
{
// Recursively visit child node
this.replaceByDepth(node.child[i], depth + 1);
i++;
}
}
// Display preorder traversal of binary tree
printPreorder(node)
{
if (node == null)
{
return;
}
var i = 0;
var temp = null;
// Display node value
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 2 1 3
/ \ |
17 12 20
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = new TreeNode(10);
tree.root.addChild(8);
tree.root.addChild(5);
// Add child node [-2,1,5] 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 [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);
// Add child node [20] in node (2)
tree.root.child[1].child[3].child[0].addChild(20);
// Before update
process.stdout.write("\n Before replace \n");
tree.printPreorder(tree.root);
// Change node value
tree.replaceByDepth(tree.root, 0);
// After update
process.stdout.write("\n After replace by depth \n");
tree.printPreorder(tree.root);
}
main();
input
Before replace
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 20 1 3
After replace by depth
0 1 2 2 3 3 4 4 2 1 2 2 2 2 3 4 3 3
# Python 3 program for
# Replace every node with depth in n-ary tree
class TreeNode :
def __init__(self, key) :
self.key = key
self.child = []
def addChild(self, key) :
t = TreeNode(key)
self.child.append(t)
class NAryTree :
def __init__(self) :
self.root = None
def replaceByDepth(self, node, depth) :
i = 0
# Update node value by depth
node.key = depth
# iterating the child of given node
while (i < len(node.child)) :
# Recursively visit child node
self.replaceByDepth(node.child[i], depth + 1)
i += 1
# Display preorder traversal of binary tree
def printPreorder(self, node) :
if (node == None) :
return
i = 0
temp = None
# Display node value
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 2 1 3
# / \ |
# 17 12 20
# -----------------------
# Constructing N-Arr tree
# First element of tree
tree.root = TreeNode(10)
tree.root.addChild(8)
tree.root.addChild(5)
# Add child node [-2,1,5] 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 [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)
# Add child node [20] in node (2)
tree.root.child[1].child[3].child[0].addChild(20)
# Before update
print("\n Before replace ")
tree.printPreorder(tree.root)
# Change node value
tree.replaceByDepth(tree.root, 0)
# After update
print("\n After replace by depth ")
tree.printPreorder(tree.root)
if __name__ == "__main__": main()
input
Before replace
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 20 1 3
After replace by depth
0 1 2 2 3 3 4 4 2 1 2 2 2 2 3 4 3 3
# Ruby program for
# Replace every node with depth in n-ary tree
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :key, :child
attr_accessor :key, :child
def initialize(key)
self.key = key
self.child = []
end
def addChild(key)
t = TreeNode.new(key)
self.child.push(t)
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 replaceByDepth(node, depth)
i = 0
# Update node value by depth
node.key = depth
# iterating the child of given node
while (i < node.child.length)
# Recursively visit child node
self.replaceByDepth(node.child[i], depth + 1)
i += 1
end
end
# Display preorder traversal of binary tree
def printPreorder(node)
if (node == nil)
return
end
i = 0
temp = nil
# Display node value
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 2 1 3
# / \ |
# 17 12 20
# -----------------------
# Constructing N-Arr tree
# First element of tree
tree.root = TreeNode.new(10)
tree.root.addChild(8)
tree.root.addChild(5)
# Add child node [-2,1,5] 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 [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)
# Add child node [20] in node (2)
tree.root.child[1].child[3].child[0].addChild(20)
# Before update
print("\n Before replace \n")
tree.printPreorder(tree.root)
# Change node value
tree.replaceByDepth(tree.root, 0)
# After update
print("\n After replace by depth \n")
tree.printPreorder(tree.root)
end
main()
input
Before replace
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 20 1 3
After replace by depth
0 1 2 2 3 3 4 4 2 1 2 2 2 2 3 4 3 3
import scala.collection.mutable._;
// Scala program for
// Replace every node with depth in n-ary tree
class TreeNode(var key: Int,
var child: ArrayBuffer[TreeNode])
{
def this(key: Int)
{
this(key, new ArrayBuffer[TreeNode]());
}
def addChild(key: Int): Unit = {
var t: TreeNode = new TreeNode(key);
this.child += t;
}
}
class NAryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def replaceByDepth(node: TreeNode, depth: Int): Unit = {
var i: Int = 0;
// Update node value by depth
node.key = depth;
// iterating the child of given node
while (i < node.child.size)
{
// Recursively visit child node
replaceByDepth(node.child(i), depth + 1);
i += 1;
}
}
// Display preorder traversal of binary tree
def printPreorder(node: TreeNode): Unit = {
if (node == null)
{
return;
}
var i: Int = 0;
var temp: TreeNode = null;
// Display node value
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 2 1 3
/ \ |
17 12 20
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = new TreeNode(10);
tree.root.addChild(8);
tree.root.addChild(5);
// Add child node [-2,1,5] 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 [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);
// Add child node [20] in node (2)
tree.root.child(1).child(3).child(0).addChild(20);
// Before update
print("\n Before replace \n");
tree.printPreorder(tree.root);
// Change node value
tree.replaceByDepth(tree.root, 0);
// After update
print("\n After replace by depth \n");
tree.printPreorder(tree.root);
}
}
input
Before replace
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 20 1 3
After replace by depth
0 1 2 2 3 3 4 4 2 1 2 2 2 2 3 4 3 3
import Foundation;
// Swift 4 program for
// Replace every node with depth in n-ary tree
class TreeNode
{
var key: Int;
var child: [TreeNode? ];
init(_ key: Int)
{
self.key = key;
self.child = [TreeNode? ]();
}
func addChild(_ key: Int)
{
let t = TreeNode(key);
self.child.append(t);
}
}
class NAryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
func replaceByDepth(_ node: TreeNode? , _ depth : Int)
{
var i = 0;
// Update node value by depth
node!.key = depth;
// iterating the child of given node
while (i < node!.child.count)
{
// Recursively visit child node
self.replaceByDepth(node!.child[i], depth + 1);
i += 1;
}
}
// Display preorder traversal of binary tree
func printPreorder(_ node: TreeNode? )
{
if (node == nil)
{
return;
}
var i = 0;
var temp : TreeNode? = nil;
// Display node value
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();
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 2 1 3
/ \ |
17 12 20
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = TreeNode(10);
tree.root!.addChild(8);
tree.root!.addChild(5);
// Add child node [-2,1,5] 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 [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);
// Add child node [20] in node (2)
tree.root!.child[1]!.child[3]!.child[0]!.addChild(20);
// Before update
print("\n Before replace ");
tree.printPreorder(tree.root);
// Change node value
tree.replaceByDepth(tree.root, 0);
// After update
print("\n After replace by depth ");
tree.printPreorder(tree.root);
}
main();
input
Before replace
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 20 1 3
After replace by depth
0 1 2 2 3 3 4 4 2 1 2 2 2 2 3 4 3 3
// Kotlin program for
// Replace every node with depth in n-ary tree
class TreeNode
{
var key: Int;
var child: MutableList<TreeNode> ;
constructor(key: Int)
{
this.key = key;
this.child = mutableListOf<TreeNode>();
}
fun addChild(key: Int): Unit
{
val t: TreeNode = TreeNode(key);
this.child.add(t);
}
}
class NAryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
fun replaceByDepth(node: TreeNode ? , depth : Int): Unit
{
var i: Int = 0;
// Update node value by depth
node!!.key = depth;
// iterating the child of given node
while (i < node.child.size)
{
// Recursively visit child node
this.replaceByDepth(node.child[i], depth + 1);
i += 1;
}
}
// Display preorder traversal of binary tree
fun printPreorder(node: TreeNode ? ): Unit
{
if (node == null)
{
return;
}
var i: Int = 0;
var temp: TreeNode ?;
// Display node value
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 2 1 3
/ \ |
17 12 20
-----------------------
Constructing N-Arr tree
*/
// First element of tree
tree.root = TreeNode(10);
tree.root?.addChild(8);
tree.root?.addChild(5);
// Add child node [-2,1,5] 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 [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);
// Add child node [20] in node (2)
tree.root!!.child[1].child[3].child[0].addChild(20);
// Before update
print("\n Before replace \n");
tree.printPreorder(tree.root);
// Change node value
tree.replaceByDepth(tree.root, 0);
// After update
print("\n After replace by depth \n");
tree.printPreorder(tree.root);
}
input
Before replace
10 8 -2 1 9 11 17 12 6 5 7 18 3 4 2 20 1 3
After replace by depth
0 1 2 2 3 3 4 4 2 1 2 2 2 2 3 4 3 3
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