Skip to main content

Sum of all leaf nodes from a N-ary Tree

Given an N-ary tree, Our goal is to find sum of all leaf node which are present in given tree. For example.

Sum of leaf nodes in N-ary tree

Here given code implementation process.

import java.util.Vector;
// Java program for
// Sum of 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()
    {
        // Initial root
        this.root = null;
    }
    public int findLeafNodeSum(TreeNode node)
    {
        if (node == null)
        {
            // When node is null
            return 0;
        }
        if (node.child.size() == 0)
        {
            // When node is leaf node
            return node.key;
        }
        // Auxiliary variables
        int i = 0;
        int sum = 0;
        // iterating the child of given node
        while (i < node.child.size())
        {
            // Visit i child and
            // Sum of all leaf nodes
            sum += findLeafNodeSum(node.child.get(i));
            // Get next child
            i++;
        }
        // Return calculated sum
        return sum;
    }
    public static void main(String[] args)
    {
        NAryTree tree = new NAryTree();
        /*
                   10
                  /   \
                 /     \
                /       \   
               8         5
              /|\       /|\  
             / | \     / | \ 
            -2 1  6   7  4  3  
              / \      \    
             9  11     -1   
               /  \
              12   -3   
            -----------------------
            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,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 [12  -3] in node (11)
        tree.root.child.get(0).child.get(1).child.get(1).addChild(12);
        tree.root.child.get(0).child.get(1).child.get(1).addChild(-3);
        // Add child node [7 4 3 ] in node (5)
        tree.root.child.get(1).addChild(7);
        tree.root.child.get(1).addChild(4);
        tree.root.child.get(1).addChild(3);
        // Add child node [-1] in node (7)
        tree.root.child.get(1).child.get(0).addChild(-1);
        // Test
        // ----
        // Leaf node [ -2 9 12 -3 6 -1 4 3]
        // sum = 28
        int ans = tree.findLeafNodeSum(tree.root);
        // Display calculated result
        System.out.println(" Leaf node sum : " + ans);
    }
}

Output

 Leaf node sum : 28
// Include header file
#include <iostream>

#include <vector>

using namespace std;
// C++ program for
// Sum of 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;
    }
    int findLeafNodeSum(TreeNode *node)
    {
        if (node == NULL)
        {
            // When node is null
            return 0;
        }
        if (node->child.size() == 0)
        {
            // When node is leaf node
            return node->key;
        }
        // Auxiliary variables
        int i = 0;
        int sum = 0;
        // iterating the child of given node
        while (i < node->child.size())
        {
            // Visit i child and
            // Sum of all leaf nodes
            sum += this->findLeafNodeSum(node->child.at(i));
            // Get next child
            i++;
        }
        // Return calculated sum
        return sum;
    }
};
int main()
{
    NAryTree *tree = new NAryTree();
    /*
                       10
                      /   \
                     /     \
                    /       \   
                   8         5
                  /|\       /|\  
                 / | \     / | \ 
                -2 1  6   7  4  3  
                  / \      \    
                 9  11     -1   
                   /  \
                  12   -3   
                -----------------------
                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,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 [12  -3] in node (11)
    tree->root->child.at(0)->child.at(1)->child.at(1)->addChild(12);
    tree->root->child.at(0)->child.at(1)->child.at(1)->addChild(-3);
    // Add child node [7 4 3 ] in node (5)
    tree->root->child.at(1)->addChild(7);
    tree->root->child.at(1)->addChild(4);
    tree->root->child.at(1)->addChild(3);
    // Add child node [-1] in node (7)
    tree->root->child.at(1)->child.at(0)->addChild(-1);
    // Test
    // ----
    // Leaf node [ -2 9 12 -3 6 -1 4 3]
    // sum = 28
    int ans = tree->findLeafNodeSum(tree->root);
    // Display calculated result
    cout << " Leaf node sum : " << ans << endl;
    return 0;
}

Output

 Leaf node sum : 28
package main
import "fmt"
// Go program for
// Sum of 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 {}
    // Initial root
    me.root = nil
    return me
}
func(this NAryTree) findLeafNodeSum(node * TreeNode) int {
    if node == nil {
        // When node is null
        return 0
    }
    if len(node.child) == 0 {
        // When node is leaf node
        return node.key
    }
    // Auxiliary variables
    var i int = 0
    var sum int = 0
    // iterating the child of given node
    for (i < len(node.child)) {
        // Visit i child and
        // Sum of all leaf nodes
        sum += this.findLeafNodeSum(node.child[i])
        // Get next child
        i++
    }
    // Return calculated sum
    return sum
}
func main() {
    var tree * NAryTree = getNAryTree()
    /*
               10
              /   \
             /     \
            /       \   
           8         5
          /|\       /|\  
         / | \     / | \ 
        -2 1  6   7  4  3  
          / \      \    
         9  11     -1   
           /  \
          12   -3   
        -----------------------
        Constructing N-Arr 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 [12  -3] in node (11)
    tree.root.child[0].child[1].child[1].addChild(12)
    tree.root.child[0].child[1].child[1].addChild(-3)
    // Add child node [7 4 3 ] in node (5)
    tree.root.child[1].addChild(7)
    tree.root.child[1].addChild(4)
    tree.root.child[1].addChild(3)
    // Add child node [-1] in node (7)
    tree.root.child[1].child[0].addChild(-1)
    // Test
    // ----
    // Leaf node [ -2 9 12 -3 6 -1 4 3]
    // sum = 28
    var ans int = tree.findLeafNodeSum(tree.root)
    // Display calculated result
    fmt.Println(" Leaf node sum : ", ans)
}

Output

 Leaf node sum : 28
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Sum of 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()
    {
        // Initial root
        this.root = null;
    }
    public int findLeafNodeSum(TreeNode node)
    {
        if (node == null)
        {
            // When node is null
            return 0;
        }
        if (node.child.Count == 0)
        {
            // When node is leaf node
            return node.key;
        }
        // Auxiliary variables
        int i = 0;
        int sum = 0;
        // iterating the child of given node
        while (i < node.child.Count)
        {
            // Visit i child and
            // Sum of all leaf nodes
            sum += this.findLeafNodeSum(node.child[i]);
            // Get next child
            i++;
        }
        // Return calculated sum
        return sum;
    }
    public static void Main(String[] args)
    {
        NAryTree tree = new NAryTree();
        /*
                   10
                  /   \
                 /     \
                /       \   
               8         5
              /|\       /|\  
             / | \     / | \ 
            -2 1  6   7  4  3  
              / \      \    
             9  11     -1   
               /  \
              12   -3   
            -----------------------
            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,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 [12  -3] in node (11)
        tree.root.child[0].child[1].child[1].addChild(12);
        tree.root.child[0].child[1].child[1].addChild(-3);
        // Add child node [7 4 3 ] in node (5)
        tree.root.child[1].addChild(7);
        tree.root.child[1].addChild(4);
        tree.root.child[1].addChild(3);
        // Add child node [-1] in node (7)
        tree.root.child[1].child[0].addChild(-1);
        // Test
        // ----
        // Leaf node [ -2 9 12 -3 6 -1 4 3]
        // sum = 28
        int ans = tree.findLeafNodeSum(tree.root);
        // Display calculated result
        Console.WriteLine(" Leaf node sum : " + ans);
    }
}

Output

 Leaf node sum : 28
<?php
// Php program for
// Sum of 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 findLeafNodeSum($node)
    {
        if ($node == NULL)
        {
            // When node is null
            return 0;
        }
        if (count($node->child) == 0)
        {
            // When node is leaf node
            return $node->key;
        }
        // Auxiliary variables
        $i = 0;
        $sum = 0;
        // iterating the child of given node
        while ($i < count($node->child))
        {
            // Visit i child and
            // Sum of all leaf nodes
            $sum += $this->findLeafNodeSum($node->child[$i]);
            // Get next child
            $i++;
        }
        // Return calculated sum
        return $sum;
    }
}

function main()
{
    $tree = new NAryTree();
    /*
               10
              /   \
             /     \
            /       \   
           8         5
          /|\       /|\  
         / | \     / | \ 
        -2 1  6   7  4  3  
          / \      \    
         9  11     -1   
           /  \
          12   -3   
        -----------------------
        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,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 [12  -3] in node (11)
    $tree->root->child[0]->child[1]->child[1]->addChild(12);
    $tree->root->child[0]->child[1]->child[1]->addChild(-3);
    // Add child node [7 4 3 ] in node (5)
    $tree->root->child[1]->addChild(7);
    $tree->root->child[1]->addChild(4);
    $tree->root->child[1]->addChild(3);
    // Add child node [-1] in node (7)
    $tree->root->child[1]->child[0]->addChild(-1);
    // Test
    // ----
    // Leaf node [ -2 9 12 -3 6 -1 4 3]
    // sum = 28
    $ans = $tree->findLeafNodeSum($tree->root);
    // Display calculated result
    echo(" Leaf node sum : ".$ans.
        "\n");
}
main();

Output

 Leaf node sum : 28
// Node JS program for
// Sum of 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;
    }
    findLeafNodeSum(node)
    {
        if (node == null)
        {
            // When node is null
            return 0;
        }
        if (node.child.length == 0)
        {
            // When node is leaf node
            return node.key;
        }
        // Auxiliary variables
        var i = 0;
        var sum = 0;
        // iterating the child of given node
        while (i < node.child.length)
        {
            // Visit i child and
            // Sum of all leaf nodes
            sum += this.findLeafNodeSum(node.child[i]);
            // Get next child
            i++;
        }
        // Return calculated sum
        return sum;
    }
}

function main()
{
    var tree = new NAryTree();
    /*
               10
              /   \
             /     \
            /       \   
           8         5
          /|\       /|\  
         / | \     / | \ 
        -2 1  6   7  4  3  
          / \      \    
         9  11     -1   
           /  \
          12   -3   
        -----------------------
        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,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 [12  -3] in node (11)
    tree.root.child[0].child[1].child[1].addChild(12);
    tree.root.child[0].child[1].child[1].addChild(-3);
    // Add child node [7 4 3 ] in node (5)
    tree.root.child[1].addChild(7);
    tree.root.child[1].addChild(4);
    tree.root.child[1].addChild(3);
    // Add child node [-1] in node (7)
    tree.root.child[1].child[0].addChild(-1);
    // Test
    // ----
    // Leaf node [ -2 9 12 -3 6 -1 4 3]
    // sum = 28
    var ans = tree.findLeafNodeSum(tree.root);
    // Display calculated result
    console.log(" Leaf node sum : " + ans);
}
main();

Output

 Leaf node sum : 28
#  Python 3 program for
#  Sum of 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 findLeafNodeSum(self, node) :
        if (node == None) :
            #  When node is null
            return 0
        
        if (len(node.child) == 0) :
            #  When node is leaf node
            return node.key
        
        #  Auxiliary variables
        i = 0
        sum = 0
        #  iterating the child of given node
        while (i < len(node.child)) :
            #  Visit i child and
            #  Sum of all leaf nodes
            sum += self.findLeafNodeSum(node.child[i])
            #  Get next child
            i += 1
        
        #  Return calculated sum
        return sum
    

def main() :
    tree = NAryTree()
    #           10
    #          /   \
    #         /     \
    #        /       \   
    #       8         5
    #      /|\       /|\  
    #     / | \     / | \ 
    #    -2 1  6   7  4  3  
    #      / \      \    
    #     9  11     -1   
    #       /  \
    #      12   -3   
    #    -----------------------
    #    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,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 [12  -3] in node (11)
    tree.root.child[0].child[1].child[1].addChild(12)
    tree.root.child[0].child[1].child[1].addChild(-3)
    #  Add child node [7 4 3 ] in node (5)
    tree.root.child[1].addChild(7)
    tree.root.child[1].addChild(4)
    tree.root.child[1].addChild(3)
    #  Add child node [-1] in node (7)
    tree.root.child[1].child[0].addChild(-1)
    #  Test
    #  ----
    #  Leaf node [ -2 9 12 -3 6 -1 4 3]
    #  sum = 28
    ans = tree.findLeafNodeSum(tree.root)
    #  Display calculated result
    print(" Leaf node sum : ", ans)

if __name__ == "__main__": main()

Output

 Leaf node sum :  28
#  Ruby program for
#  Sum of 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 findLeafNodeSum(node) 
        if (node == nil) 
            #  When node is null
            return 0
        end

        if (node.child.length == 0) 
            #  When node is leaf node
            return node.key
        end

        #  Auxiliary variables
        i = 0
        sum = 0
        #  iterating the child of given node
        while (i < node.child.length) 
            #  Visit i child and
            #  Sum of all leaf nodes
            sum += self.findLeafNodeSum(node.child[i])
            #  Get next child
            i += 1
        end

        #  Return calculated sum
        return sum
    end

end

def main() 
    tree = NAryTree.new()
    #           10
    #          /   \
    #         /     \
    #        /       \   
    #       8         5
    #      /|\       /|\  
    #     / | \     / | \ 
    #    -2 1  6   7  4  3  
    #      / \      \    
    #     9  11     -1   
    #       /  \
    #      12   -3   
    #    -----------------------
    #    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,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 [12  -3] in node (11)
    tree.root.child[0].child[1].child[1].addChild(12)
    tree.root.child[0].child[1].child[1].addChild(-3)
    #  Add child node [7 4 3 ] in node (5)
    tree.root.child[1].addChild(7)
    tree.root.child[1].addChild(4)
    tree.root.child[1].addChild(3)
    #  Add child node [-1] in node (7)
    tree.root.child[1].child[0].addChild(-1)
    #  Test
    #  ----
    #  Leaf node [ -2 9 12 -3 6 -1 4 3]
    #  sum = 28
    ans = tree.findLeafNodeSum(tree.root)
    #  Display calculated result
    print(" Leaf node sum : ", ans, "\n")
end

main()

Output

 Leaf node sum : 28

import scala.collection.mutable._;
// Scala program for
// Sum of 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 findLeafNodeSum(node: TreeNode): Int = {
        if (node == null)
        {
            // When node is null
            return 0;
        }
        if (node.child.size == 0)
        {
            // When node is leaf node
            return node.key;
        }
        // Auxiliary variables
        var i: Int = 0;
        var sum: Int = 0;
        // iterating the child of given node
        while (i < node.child.size)
        {
            // Visit i child and
            // Sum of all leaf nodes
            sum += findLeafNodeSum(node.child(i));
            // Get next child
            i += 1;
        }
        // Return calculated sum
        return sum;
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var tree: NAryTree = new NAryTree();
        /*
                   10
                  /   \
                 /     \
                /       \   
               8         5
              /|\       /|\  
             / | \     / | \ 
            -2 1  6   7  4  3  
              / \      \    
             9  11     -1   
               /  \
              12   -3   
            -----------------------
            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,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 [12  -3] in node (11)
        tree.root.child(0).child(1).child(1).addChild(12);
        tree.root.child(0).child(1).child(1).addChild(-3);
        // Add child node [7 4 3 ] in node (5)
        tree.root.child(1).addChild(7);
        tree.root.child(1).addChild(4);
        tree.root.child(1).addChild(3);
        // Add child node [-1] in node (7)
        tree.root.child(1).child(0).addChild(-1);
        // Test
        // ----
        // Leaf node [ -2 9 12 -3 6 -1 4 3]
        // sum = 28
        var ans: Int = tree.findLeafNodeSum(tree.root);
        // Display calculated result
        println(" Leaf node sum : " + ans);
    }
}

Output

 Leaf node sum : 28
import Foundation;
// Swift 4 program for
// Sum of 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 findLeafNodeSum(_ node: TreeNode? ) -> Int
    {
        if (node == nil)
        {
            // When node is null
            return 0;
        }
        if (node!.child.count == 0)
        {
            // When node is leaf node
            return node!.key;
        }
        // Auxiliary variables
        var i: Int = 0;
        var sum: Int = 0;
        // iterating the child of given node
        while (i < node!.child.count)
        {
            // Visit i child and
            // Sum of all leaf nodes
            sum += self.findLeafNodeSum(node!.child[i]);
            // Get next child
            i += 1;
        }
        // Return calculated sum
        return sum;
    }
}
func main()
{
    let tree: NAryTree = NAryTree();
    /*
               10
              /   \
             /     \
            /       \   
           8         5
          /|\       /|\  
         / | \     / | \ 
        -2 1  6   7  4  3  
          / \      \    
         9  11     -1   
           /  \
          12   -3   
        -----------------------
        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,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 [12  -3] in node (11)
    tree.root!.child[0]!.child[1]!.child[1]!.addChild(12);
    tree.root!.child[0]!.child[1]!.child[1]!.addChild(-3);
    // Add child node [7 4 3 ] in node (5)
    tree.root!.child[1]!.addChild(7);
    tree.root!.child[1]!.addChild(4);
    tree.root!.child[1]!.addChild(3);
    // Add child node [-1] in node (7)
    tree.root!.child[1]!.child[0]!.addChild(-1);
    // Test
    // ----
    // Leaf node [ -2 9 12 -3 6 -1 4 3]
    // sum = 28
    let ans: Int = tree.findLeafNodeSum(tree.root);
    // Display calculated result
    print(" Leaf node sum : ", ans);
}
main();

Output

 Leaf node sum :  28
// Kotlin program for
// Sum of 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 findLeafNodeSum(node: TreeNode ? ): Int
    {
        if (node == null)
        {
            // When node is null
            return 0;
        }
        if (node.child.size == 0)
        {
            // When node is leaf node
            return node.key;
        }
        // Auxiliary variables
        var i: Int = 0;
        var sum: Int = 0;
        // iterating the child of given node
        while (i < node.child.size)
        {
            // Visit i child and
            // Sum of all leaf nodes
            sum += this.findLeafNodeSum(node.child[i]);
            // Get next child
            i += 1;
        }
        // Return calculated sum
        return sum;
    }
}
fun main(args: Array < String > ): Unit
{
    val tree: NAryTree = NAryTree();
    /*
               10
              /   \
             /     \
            /       \   
           8         5
          /|\       /|\  
         / | \     / | \ 
        -2 1  6   7  4  3  
          / \      \    
         9  11     -1   
           /  \
          12   -3   
        -----------------------
        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,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 [12  -3] in node (11)
    tree.root!!.child[0].child[1].child[1].addChild(12);
    tree.root!!.child[0].child[1].child[1].addChild(-3);
    // Add child node [7 4 3 ] in node (5)
    tree.root!!.child[1].addChild(7);
    tree.root!!.child[1].addChild(4);
    tree.root!!.child[1].addChild(3);
    // Add child node [-1] in node (7)
    tree.root!!.child[1].child[0].addChild(-1);
    // Test
    // ----
    // Leaf node [ -2 9 12 -3 6 -1 4 3]
    // sum = 28
    val ans: Int = tree.findLeafNodeSum(tree.root);
    // Display calculated result
    println(" Leaf node sum : " + ans);
}

Output

 Leaf node sum : 28
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