Skip to main content

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
Last updated on by Kalkicode




Comment

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