Difference between sums of odd and even levels in n-ary tree
Here given code implementation process.
import java.util.Vector;
// Java program for
// Difference between sums of odd level and even
// level nodes in an 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 int even;
public int odd;
public NAryTree()
{
this.root = null;
this.even = 0;
this.odd = 0;
}
public void findLevelSum(TreeNode node, int level)
{
if (node == null)
{
return;
}
int i = 0;
if (level % 2 == 0)
{
// Sum of even level node
this.even += node.key;
}
else
{
// Sum of odd level node
this.odd += node.key;
}
// iterating the child of given node
while (i < node.child.size())
{
// Visit to child subtree
findLevelSum(node.child.get(i), level + 1);
// Change child node
i++;
}
}
public void levelSumDifference()
{
this.even = 0;
this.odd = 0;
this.findLevelSum(this.root, 0);
System.out.println(" Difference : " + (this.even - this.odd));
}
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
-----------------------
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 [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);
/*
10 Level 0
/ \
/ \
/ \
8 5 Level 1
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4 Level 2
/ \ /| \
9 11 2 1 3 Level 3
/ \
17 12 Level 4
-----------------------
Even level node sum
[10 + (-2) + 1 + 6 + 7 + 18 + 3 + 4 + 17 + 12] = 76
Odd level node sum
[8 + 5 + 9 + 11 + 2 + 1 + 3] = 39
----------------------------------------
(76-39) = 37
*/
tree.levelSumDifference();
}
}
Output
Difference : 37
package main
import "fmt"
// Go program for
// Difference between sums of odd level and even
// level nodes in an 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
even int
odd int
}
func getNAryTree() * NAryTree {
var me *NAryTree = &NAryTree {}
me.root = nil
me.even = 0
me.odd = 0
return me
}
func(this *NAryTree) findLevelSum(node * TreeNode, level int) {
if node == nil {
return
}
var i int = 0
if level % 2 == 0 {
// Sum of even level node
this.even += node.key
} else {
// Sum of odd level node
this.odd += node.key
}
// iterating the child of given node
for (i < len(node.child)) {
// Visit to child subtree
this.findLevelSum(node.child[i], level + 1)
// Change child node
i++
}
}
func(this *NAryTree) levelSumDifference() {
this.even = 0
this.odd = 0
this.findLevelSum(this.root, 0)
fmt.Println(" Difference : ", (this.even - this.odd))
}
func main() {
var tree * NAryTree = getNAryTree()
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 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 [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)
/*
10 Level 0
/ \
/ \
/ \
8 5 Level 1
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4 Level 2
/ \ /| \
9 11 2 1 3 Level 3
/ \
17 12 Level 4
-----------------------
Even level node sum
[10 + (-2) + 1 + 6 + 7 + 18 + 3 + 4 + 17 + 12] = 76
Odd level node sum
[8 + 5 + 9 + 11 + 2 + 1 + 3] = 39
----------------------------------------
(76-39) = 37
*/
tree.levelSumDifference()
}
Output
Difference : 37
// Include header file
#include <iostream>
#include <vector>
using namespace std;
// C++ program for
// Difference between sums of odd level and even
// level nodes in an 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;
int even;
int odd;
NAryTree()
{
this->root = NULL;
this->even = 0;
this->odd = 0;
}
void findLevelSum(TreeNode *node, int level)
{
if (node == NULL)
{
return;
}
int i = 0;
if (level % 2 == 0)
{
// Sum of even level node
this->even += node->key;
}
else
{
// Sum of odd level node
this->odd += node->key;
}
// iterating the child of given node
while (i < node->child.size())
{
// Visit to child subtree
this->findLevelSum(node->child.at(i), level + 1);
// Change child node
i++;
}
}
void levelSumDifference()
{
this->even = 0;
this->odd = 0;
this->findLevelSum(this->root, 0);
cout << " Difference : " << (this->even - this->odd) << endl;
}
};
int main()
{
NAryTree *tree = new NAryTree();
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 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 [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);
/*
10 Level 0
/ \
/ \
/ \
8 5 Level 1
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4 Level 2
/ \ /| \
9 11 2 1 3 Level 3
/ \
17 12 Level 4
-----------------------
Even level node sum
[10 + (-2) + 1 + 6 + 7 + 18 + 3 + 4 + 17 + 12] = 76
Odd level node sum
[8 + 5 + 9 + 11 + 2 + 1 + 3] = 39
----------------------------------------
(76-39) = 37
*/
tree->levelSumDifference();
return 0;
}
Output
Difference : 37
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Difference between sums of odd level and even
// level nodes in an 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 int even;
public int odd;
public NAryTree()
{
this.root = null;
this.even = 0;
this.odd = 0;
}
public void findLevelSum(TreeNode node, int level)
{
if (node == null)
{
return;
}
int i = 0;
if (level % 2 == 0)
{
// Sum of even level node
this.even += node.key;
}
else
{
// Sum of odd level node
this.odd += node.key;
}
// iterating the child of given node
while (i < node.child.Count)
{
// Visit to child subtree
this.findLevelSum(node.child[i], level + 1);
// Change child node
i++;
}
}
public void levelSumDifference()
{
this.even = 0;
this.odd = 0;
this.findLevelSum(this.root, 0);
Console.WriteLine(" Difference : " + (this.even - this.odd));
}
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
-----------------------
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 [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);
/*
10 Level 0
/ \
/ \
/ \
8 5 Level 1
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4 Level 2
/ \ /| \
9 11 2 1 3 Level 3
/ \
17 12 Level 4
-----------------------
Even level node sum
[10 + (-2) + 1 + 6 + 7 + 18 + 3 + 4 + 17 + 12] = 76
Odd level node sum
[8 + 5 + 9 + 11 + 2 + 1 + 3] = 39
----------------------------------------
(76-39) = 37
*/
tree.levelSumDifference();
}
}
Output
Difference : 37
<?php
// Php program for
// Difference between sums of odd level and even
// level nodes in an 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 $even;
public $odd;
public function __construct()
{
$this->root = NULL;
$this->even = 0;
$this->odd = 0;
}
public function findLevelSum($node, $level)
{
if ($node == NULL)
{
return;
}
$i = 0;
if ($level % 2 == 0)
{
// Sum of even level node
$this->even += $node->key;
}
else
{
// Sum of odd level node
$this->odd += $node->key;
}
// iterating the child of given node
while ($i < count($node->child))
{
// Visit to child subtree
$this->findLevelSum($node->child[$i], $level + 1);
// Change child node
$i++;
}
}
public function levelSumDifference()
{
$this->even = 0;
$this->odd = 0;
$this->findLevelSum($this->root, 0);
echo(" Difference : ".($this->even - $this->odd).
"\n");
}
}
function main()
{
$tree = new NAryTree();
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 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 [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);
/*
10 Level 0
/ \
/ \
/ \
8 5 Level 1
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4 Level 2
/ \ /| \
9 11 2 1 3 Level 3
/ \
17 12 Level 4
-----------------------
Even level node sum
[10 + (-2) + 1 + 6 + 7 + 18 + 3 + 4 + 17 + 12] = 76
Odd level node sum
[8 + 5 + 9 + 11 + 2 + 1 + 3] = 39
----------------------------------------
(76-39) = 37
*/
$tree->levelSumDifference();
}
main();
Output
Difference : 37
// Node JS program for
// Difference between sums of odd level and even
// level nodes in an 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;
this.even = 0;
this.odd = 0;
}
findLevelSum(node, level)
{
if (node == null)
{
return;
}
var i = 0;
if (level % 2 == 0)
{
// Sum of even level node
this.even += node.key;
}
else
{
// Sum of odd level node
this.odd += node.key;
}
// iterating the child of given node
while (i < node.child.length)
{
// Visit to child subtree
this.findLevelSum(node.child[i], level + 1);
// Change child node
i++;
}
}
levelSumDifference()
{
this.even = 0;
this.odd = 0;
this.findLevelSum(this.root, 0);
console.log(" Difference : " + (this.even - this.odd));
}
}
function main()
{
var tree = new NAryTree();
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 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 [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);
/*
10 Level 0
/ \
/ \
/ \
8 5 Level 1
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4 Level 2
/ \ /| \
9 11 2 1 3 Level 3
/ \
17 12 Level 4
-----------------------
Even level node sum
[10 + (-2) + 1 + 6 + 7 + 18 + 3 + 4 + 17 + 12] = 76
Odd level node sum
[8 + 5 + 9 + 11 + 2 + 1 + 3] = 39
----------------------------------------
(76-39) = 37
*/
tree.levelSumDifference();
}
main();
Output
Difference : 37
# Python 3 program for
# Difference between sums of odd level and even
# level nodes in an 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
self.even = 0
self.odd = 0
def findLevelSum(self, node, level) :
if (node == None) :
return
i = 0
if (level % 2 == 0) :
# Sum of even level node
self.even += node.key
else :
# Sum of odd level node
self.odd += node.key
# iterating the child of given node
while (i < len(node.child)) :
# Visit to child subtree
self.findLevelSum(node.child[i], level + 1)
# Change child node
i += 1
def levelSumDifference(self) :
self.even = 0
self.odd = 0
self.findLevelSum(self.root, 0)
print(" Difference : ", (self.even - self.odd))
def main() :
tree = NAryTree()
# 10
# / \
# / \
# / \
# 8 5
# /|\ /|\ \
# / | \ / | \ \
# -2 1 6 7 18 3 4
# / \ /| \
# 9 11 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 [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)
# 10 Level 0
# / \
# / \
# / \
# 8 5 Level 1
# /|\ /|\ \
# / | \ / | \ \
# -2 1 6 7 18 3 4 Level 2
# / \ /| \
# 9 11 2 1 3 Level 3
# / \
# 17 12 Level 4
# -----------------------
# Even level node sum
# [10 + (-2) + 1 + 6 + 7 + 18 + 3 + 4 + 17 + 12] = 76
# Odd level node sum
# [8 + 5 + 9 + 11 + 2 + 1 + 3] = 39
# ----------------------------------------
# (76-39) = 37
tree.levelSumDifference()
if __name__ == "__main__": main()
Output
Difference : 37
# Ruby program for
# Difference between sums of odd level and even
# level nodes in an 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, :even, :odd
attr_accessor :root, :even, :odd
def initialize()
self.root = nil
self.even = 0
self.odd = 0
end
def findLevelSum(node, level)
if (node == nil)
return
end
i = 0
if (level % 2 == 0)
# Sum of even level node
self.even += node.key
else
# Sum of odd level node
self.odd += node.key
end
# iterating the child of given node
while (i < node.child.length)
# Visit to child subtree
self.findLevelSum(node.child[i], level + 1)
# Change child node
i += 1
end
end
def levelSumDifference()
self.even = 0
self.odd = 0
self.findLevelSum(self.root, 0)
print(" Difference : ", (self.even - self.odd), "\n")
end
end
def main()
tree = NAryTree.new()
# 10
# / \
# / \
# / \
# 8 5
# /|\ /|\ \
# / | \ / | \ \
# -2 1 6 7 18 3 4
# / \ /| \
# 9 11 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 [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)
# 10 Level 0
# / \
# / \
# / \
# 8 5 Level 1
# /|\ /|\ \
# / | \ / | \ \
# -2 1 6 7 18 3 4 Level 2
# / \ /| \
# 9 11 2 1 3 Level 3
# / \
# 17 12 Level 4
# -----------------------
# Even level node sum
# [10 + (-2) + 1 + 6 + 7 + 18 + 3 + 4 + 17 + 12] = 76
# Odd level node sum
# [8 + 5 + 9 + 11 + 2 + 1 + 3] = 39
# ----------------------------------------
# (76-39) = 37
tree.levelSumDifference()
end
main()
Output
Difference : 37
import scala.collection.mutable._;
// Scala program for
// Difference between sums of odd level and even
// level nodes in an 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,
var even: Int,
var odd: Int)
{
def this()
{
this(null, 0, 0);
}
def findLevelSum(node: TreeNode, level: Int): Unit = {
if (node == null)
{
return;
}
var i: Int = 0;
if (level % 2 == 0)
{
// Sum of even level node
this.even += node.key;
}
else
{
// Sum of odd level node
this.odd += node.key;
}
// iterating the child of given node
while (i < node.child.size)
{
// Visit to child subtree
findLevelSum(node.child(i), level + 1);
// Change child node
i += 1;
}
}
def levelSumDifference(): Unit = {
this.even = 0;
this.odd = 0;
this.findLevelSum(this.root, 0);
println(" Difference : " + (this.even - this.odd));
}
}
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
-----------------------
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 [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);
/*
10 Level 0
/ \
/ \
/ \
8 5 Level 1
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4 Level 2
/ \ /| \
9 11 2 1 3 Level 3
/ \
17 12 Level 4
-----------------------
Even level node sum
[10 + (-2) + 1 + 6 + 7 + 18 + 3 + 4 + 17 + 12] = 76
Odd level node sum
[8 + 5 + 9 + 11 + 2 + 1 + 3] = 39
----------------------------------------
(76-39) = 37
*/
tree.levelSumDifference();
}
}
Output
Difference : 37
import Foundation;
// Swift 4 program for
// Difference between sums of odd level and even
// level nodes in an 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? ;
var even: Int;
var odd: Int;
init()
{
self.root = nil;
self.even = 0;
self.odd = 0;
}
func findLevelSum(_ node: TreeNode? , _ level : Int)
{
if (node == nil)
{
return;
}
var i: Int = 0;
if (level % 2 == 0)
{
// Sum of even level node
self.even += node!.key;
}
else
{
// Sum of odd level node
self.odd += node!.key;
}
// iterating the child of given node
while (i < node!.child.count)
{
// Visit to child subtree
self.findLevelSum(node!.child[i], level + 1);
// Change child node
i += 1;
}
}
func levelSumDifference()
{
self.even = 0;
self.odd = 0;
self.findLevelSum(self.root, 0);
print(" Difference : ", (self.even - self.odd));
}
}
func main()
{
let tree: NAryTree = NAryTree();
/*
10
/ \
/ \
/ \
8 5
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4
/ \ /| \
9 11 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 [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);
/*
10 Level 0
/ \
/ \
/ \
8 5 Level 1
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4 Level 2
/ \ /| \
9 11 2 1 3 Level 3
/ \
17 12 Level 4
-----------------------
Even level node sum
[10 + (-2) + 1 + 6 + 7 + 18 + 3 + 4 + 17 + 12] = 76
Odd level node sum
[8 + 5 + 9 + 11 + 2 + 1 + 3] = 39
----------------------------------------
(76-39) = 37
*/
tree.levelSumDifference();
}
main();
Output
Difference : 37
// Kotlin program for
// Difference between sums of odd level and even
// level nodes in an 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 ? ;
var even: Int;
var odd: Int;
constructor()
{
this.root = null;
this.even = 0;
this.odd = 0;
}
fun findLevelSum(node: TreeNode ? , level : Int): Unit
{
if (node == null)
{
return;
}
var i: Int = 0;
if (level % 2 == 0)
{
// Sum of even level node
this.even += node.key;
}
else
{
// Sum of odd level node
this.odd += node.key;
}
// iterating the child of given node
while (i < node.child.size)
{
// Visit to child subtree
this.findLevelSum(node.child[i], level + 1);
// Change child node
i += 1;
}
}
fun levelSumDifference(): Unit
{
this.even = 0;
this.odd = 0;
this.findLevelSum(this.root, 0);
println(" Difference : " + (this.even - this.odd));
}
}
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
-----------------------
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 [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);
/*
10 Level 0
/ \
/ \
/ \
8 5 Level 1
/|\ /|\ \
/ | \ / | \ \
-2 1 6 7 18 3 4 Level 2
/ \ /| \
9 11 2 1 3 Level 3
/ \
17 12 Level 4
-----------------------
Even level node sum
[10 + (-2) + 1 + 6 + 7 + 18 + 3 + 4 + 17 + 12] = 76
Odd level node sum
[8 + 5 + 9 + 11 + 2 + 1 + 3] = 39
----------------------------------------
(76-39) = 37
*/
tree.levelSumDifference();
}
Output
Difference : 37
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