Skip to main content

Sum of nodes in top view of binary tree efficiently

sum of top view of binary tree

Here given code implementation process.

import java.util.HashMap;
// Java program for
// Sum of nodes in top view of binary tree efficiently
// Using Map
class TreeNode
{
    // Data value 
    public int data;
    // Indicates left and right subtree
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
public class BinaryTree
{
    public TreeNode root;
    public BinaryTree()
    {
        this.root = null;
    }
    public void findTopNode(TreeNode node, 
                             HashMap < Integer, Integer > record, 
                             int distance, int level)
    {
        if (node != null)
        {
            if (!record.containsKey(distance))
            {
                // Get top view element
                record.put(distance, node.data);
            }
            // Visit left subtree
            findTopNode(node.left, record, distance - 1, level + 1);
            // Visit right subtree
            findTopNode(node.right, record, distance + 1, level + 1);
        }
    }
    public void topViewNodeSum()
    {
        if (this.root != null)
        {
            // Use to collect elements of top view
            HashMap < Integer, Integer > record = 
              new HashMap < Integer, Integer > ();
            findTopNode(this.root, record, 0, 0);
            int sum = 0;
            // Sum top view nodes
            for (int info: record.keySet())
            {
                sum += record.get(info);
            }
            // Display calculated result
            System.out.println(" Sum : " + sum);
        }
    }
    public static void main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        /* 
         Make A Binary Tree
         -----------------------
              1
             /  \
            2    3
           /    /  \
          4    5    6
           \         \
            7         9
           / \       /
         -2   11    10
         /
        8 
      */
        // Add Binary tree nodes
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.right.right = new TreeNode(6);
        tree.root.right.right.right = new TreeNode(9);
        tree.root.right.left = new TreeNode(5);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.left.right = new TreeNode(7);
        tree.root.left.left.right.left = new TreeNode(-2);
        tree.root.left.left.right.left.left = new TreeNode(8);
        tree.root.left.left.right.right = new TreeNode(11);
        tree.root.right.right.right.left = new TreeNode(10);
        /*
                ↆ
                1
              ↆ/ \ↆ
              2   3
            ↆ/    /\ↆ
            4    5  6
             \       \ↆ
              7       9
             / \     /
           -2   11  10
          ↆ/
          8 
          ----------------
             Top element
          8  4  2  1 3  6  9 
          ----------------
             Sum : 33
        */
        tree.topViewNodeSum();
    }
}

Output

 Sum : 33
// Include header file
#include <iostream>
#include <unordered_map>

using namespace std;
// C++ program for
// Sum of nodes in top view of binary tree efficiently
// Using Map
class TreeNode
{
    public:
    // Data value
    int data;
    // Indicates left and right subtree
    TreeNode *left;
    TreeNode *right;
    TreeNode(int data)
    {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
class BinaryTree
{
    public: TreeNode *root;
    BinaryTree()
    {
        this->root = NULL;
    }
    void findTopNode(TreeNode *node, 
                     unordered_map < int, int > &record, 
                     int distance, 
                     int level)
    {
        if (node != NULL)
        {
            if (record.find(distance) == record.end())
            {
                // Get top view element
                record[distance] = node->data;
            }
            // Visit left subtree
            this->findTopNode(node->left, record, distance - 1, level + 1);
            // Visit right subtree
            this->findTopNode(node->right, record, distance + 1, level + 1);
        }
    }
    void topViewNodeSum()
    {
        if (this->root != NULL)
        {
            // Use to collect elements of top view
            unordered_map < int, int > record;
            this->findTopNode(this->root, record, 0, 0);
            int sum = 0;
            // Sum top view nodes
            for (auto &info: record)
            {
                sum += record[info.first];
            }
            // Display calculated result
            cout << " Sum : " << sum << endl;
        }
    }
};
int main()
{
    BinaryTree *tree = new BinaryTree();
    /*
         Make A Binary Tree
         -----------------------
              1
             /  \
            2    3
           /    /  \
          4    5    6
           \         \
            7         9
           / \       /
         -2   11    10
         /
        8           
    */
    // Add Binary tree nodes
    tree->root = new TreeNode(1);
    tree->root->left = new TreeNode(2);
    tree->root->right = new TreeNode(3);
    tree->root->right->right = new TreeNode(6);
    tree->root->right->right->right = new TreeNode(9);
    tree->root->right->left = new TreeNode(5);
    tree->root->left->left = new TreeNode(4);
    tree->root->left->left->right = new TreeNode(7);
    tree->root->left->left->right->left = new TreeNode(-2);
    tree->root->left->left->right->left->left = new TreeNode(8);
    tree->root->left->left->right->right = new TreeNode(11);
    tree->root->right->right->right->left = new TreeNode(10);
    /*
            ↆ
            1
          ↆ/ \ↆ
          2   3
        ↆ/    /\ↆ
        4    5  6
         \       \ↆ
          7       9
         / \     /
       -2   11  10
      ↆ/
      8 
      ----------------
         Top element
      8  4  2  1 3  6  9 
      ----------------
         Sum : 33
    */
    tree->topViewNodeSum();
    return 0;
}

Output

 Sum : 33
package main
import "fmt"
// Go program for
// Sum of nodes in top view of binary tree efficiently
// Using Map
type TreeNode struct {
    // Data value
    data int
    // Indicates left and right subtree
    left * TreeNode
    right * TreeNode
}
func getTreeNode(data int) * TreeNode {
    var me *TreeNode = &TreeNode {}
    me.data = data
    me.left = nil
    me.right = nil
    return me
}
type BinaryTree struct {
    root * TreeNode
}
func getBinaryTree() * BinaryTree {
    var me *BinaryTree = &BinaryTree {}
    me.root = nil
    return me
}
func(this BinaryTree) findTopNode(node * TreeNode, 
    record map[int] int, distance int, level int) {
    if node != nil {
        if _, found := record[distance] ; !found {
            // Get top view element
            record[distance] = node.data
        }
        // Visit left subtree
        this.findTopNode(node.left, record, distance - 1, level + 1)
        // Visit right subtree
        this.findTopNode(node.right, record, distance + 1, level + 1)
    }
}
func(this BinaryTree) topViewNodeSum() {
    if this.root != nil {
        // Use to collect elements of top view
        var record = make(map[int] int)
        this.findTopNode(this.root, record, 0, 0)
        var sum int = 0
        // Sum top view nodes
        for _, v := range record {
            sum += v
        }
        // Display calculated result
        fmt.Println(" Sum : ", sum)
    }
}
func main() {
    var tree * BinaryTree = getBinaryTree()
    /* 
         Make A Binary Tree
         -----------------------
              1
             /  \
            2    3
           /    /  \
          4    5    6
           \         \
            7         9
           / \       /
         -2   11    10
         /
        8 
    */
    // Add Binary tree nodes
    tree.root = getTreeNode(1)
    tree.root.left = getTreeNode(2)
    tree.root.right = getTreeNode(3)
    tree.root.right.right = getTreeNode(6)
    tree.root.right.right.right = getTreeNode(9)
    tree.root.right.left = getTreeNode(5)
    tree.root.left.left = getTreeNode(4)
    tree.root.left.left.right = getTreeNode(7)
    tree.root.left.left.right.left = getTreeNode(-2)
    tree.root.left.left.right.left.left = getTreeNode(8)
    tree.root.left.left.right.right = getTreeNode(11)
    tree.root.right.right.right.left = getTreeNode(10)
    /*
            ↆ
            1
          ↆ/ \ↆ
          2   3
        ↆ/    /\ↆ
        4    5  6
         \       \ↆ
          7       9
         / \     /
       -2   11  10
      ↆ/
      8 
      ----------------
         Top element
      8  4  2  1 3  6  9 
      ----------------
         Sum : 33
    */
    tree.topViewNodeSum()
}

Output

 Sum : 33
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Sum of nodes in top view of binary tree efficiently
// Using Map
public class TreeNode
{
    // Data value
    public int data;
    // Indicates left and right subtree
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
public class BinaryTree
{
    public TreeNode root;
    public BinaryTree()
    {
        this.root = null;
    }
    public void findTopNode(TreeNode node, 
                             Dictionary < int, int > record, 
                             int distance, int level)
    {
        if (node != null)
        {
            if (!record.ContainsKey(distance))
            {
                // Get top view element
                record.Add(distance, node.data);
            }
            // Visit left subtree
            this.findTopNode(node.left, record, distance - 1, level + 1);
            // Visit right subtree
            this.findTopNode(node.right, record, distance + 1, level + 1);
        }
    }
    public void topViewNodeSum()
    {
        if (this.root != null)
        {
            // Use to collect elements of top view
            Dictionary < int, int > record = new Dictionary < int, int > ();
            this.findTopNode(this.root, record, 0, 0);
            int sum = 0;
            // Sum top view nodes
            foreach(KeyValuePair < int, int > node in record)
            {
                sum += node.Value;
            }
            // Display calculated result
            Console.WriteLine(" Sum : " + sum);
        }
    }
    public static void Main(String[] args)
    {
        BinaryTree tree = new BinaryTree();
        /* 
             Make A Binary Tree
             -----------------------
                  1
                 /  \
                2    3
               /    /  \
              4    5    6
               \         \
                7         9
               / \       /
             -2   11    10
             /
            8               
        */
        // Add Binary tree nodes
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.right.right = new TreeNode(6);
        tree.root.right.right.right = new TreeNode(9);
        tree.root.right.left = new TreeNode(5);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.left.right = new TreeNode(7);
        tree.root.left.left.right.left = new TreeNode(-2);
        tree.root.left.left.right.left.left = new TreeNode(8);
        tree.root.left.left.right.right = new TreeNode(11);
        tree.root.right.right.right.left = new TreeNode(10);
        /*
                ↆ
                1
              ↆ/ \ↆ
              2   3
            ↆ/    /\ↆ
            4    5  6
             \       \ↆ
              7       9
             / \     /
           -2   11  10
          ↆ/
          8 
          ----------------
             Top element
          8  4  2  1 3  6  9 
          ----------------
             Sum : 33
        */
        tree.topViewNodeSum();
    }
}

Output

 Sum : 33
<?php
// Php program for
// Sum of nodes in top view of binary tree efficiently
// Using Map
class TreeNode
{
    // Data value
    public $data;
    // Indicates left and right subtree
    public $left;
    public $right;
    public  function __construct($data)
    {
        $this->data = $data;
        $this->left = NULL;
        $this->right = NULL;
    }
}
class BinaryTree
{
    public $root;
    public  function __construct()
    {
        $this->root = NULL;
    }
    public  function findTopNode($node, &$record, $distance, $level)
    {
        if ($node != NULL)
        {
            if (!array_key_exists($distance, $record))
            {
                // Get top view element
                $record[$distance] = $node->data;
            }
            // Visit left subtree
            $this->findTopNode($node->left, 
                               $record, $distance - 1, $level + 1);
            // Visit right subtree
            $this->findTopNode($node->right, 
                               $record, $distance + 1, $level + 1);
        }
    }
    public  function topViewNodeSum()
    {
        if ($this->root != NULL)
        {
            // Use to collect elements of top view
            $record = array();
            $this->findTopNode($this->root, $record, 0, 0);
            $sum = 0;
            // Sum top view nodes
            foreach($record as $key => $value)
            {
                $sum += $value;
            }
            // Display calculated result
            echo(" Sum : ".$sum."\n");
        }
    }
}

function main()
{
    $tree = new BinaryTree();
    /* 
         Make A Binary Tree
         -----------------------
              1
             /  \
            2    3
           /    /  \
          4    5    6
           \         \
            7         9
           / \       /
         -2   11    10
         /
        8           
    */
    // Add Binary tree nodes
    $tree->root = new TreeNode(1);
    $tree->root->left = new TreeNode(2);
    $tree->root->right = new TreeNode(3);
    $tree->root->right->right = new TreeNode(6);
    $tree->root->right->right->right = new TreeNode(9);
    $tree->root->right->left = new TreeNode(5);
    $tree->root->left->left = new TreeNode(4);
    $tree->root->left->left->right = new TreeNode(7);
    $tree->root->left->left->right->left = new TreeNode(-2);
    $tree->root->left->left->right->left->left = new TreeNode(8);
    $tree->root->left->left->right->right = new TreeNode(11);
    $tree->root->right->right->right->left = new TreeNode(10);
    /*
            ↆ
            1
          ↆ/ \ↆ
          2   3
        ↆ/    /\ↆ
        4    5  6
         \       \ↆ
          7       9
         / \     /
       -2   11  10
      ↆ/
      8 
      ----------------
         Top element
      8  4  2  1 3  6  9 
      ----------------
         Sum : 33
    */
    $tree->topViewNodeSum();
}
main();

Output

 Sum : 33
// Node JS program for
// Sum of nodes in top view of binary tree efficiently
// Using Map
class TreeNode
{
    constructor(data)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class BinaryTree
{
    constructor()
    {
        this.root = null;
    }
    findTopNode(node, record, distance, level)
    {
        if (node != null)
        {
            if (!record.has(distance))
            {
                // Get top view element
                record.set(distance, node.data);
            }
            // Visit left subtree
            this.findTopNode(node.left, 
                             record, distance - 1, level + 1);
            // Visit right subtree
            this.findTopNode(node.right, 
                             record, distance + 1, level + 1);
        }
    }
    topViewNodeSum()
    {
        if (this.root != null)
        {
            // Use to collect elements of top view
            var record = new Map();
            this.findTopNode(this.root, record, 0, 0);
            var sum = 0;
            // Sum top view nodes
            for (let [key, value] of record)
            {
                sum += value;
            }
            // Display calculated result
            console.log(" Sum : " + sum);
        }
    }
}

function main()
{
    var tree = new BinaryTree();
    /* 
         Make A Binary Tree
         -----------------------
              1
             /  \
            2    3
           /    /  \
          4    5    6
           \         \
            7         9
           / \       /
         -2   11    10
         /
        8 
          
    */
    // Add Binary tree nodes
    tree.root = new TreeNode(1);
    tree.root.left = new TreeNode(2);
    tree.root.right = new TreeNode(3);
    tree.root.right.right = new TreeNode(6);
    tree.root.right.right.right = new TreeNode(9);
    tree.root.right.left = new TreeNode(5);
    tree.root.left.left = new TreeNode(4);
    tree.root.left.left.right = new TreeNode(7);
    tree.root.left.left.right.left = new TreeNode(-2);
    tree.root.left.left.right.left.left = new TreeNode(8);
    tree.root.left.left.right.right = new TreeNode(11);
    tree.root.right.right.right.left = new TreeNode(10);
    /*
            ↆ
            1
          ↆ/ \ↆ
          2   3
        ↆ/    /\ↆ
        4    5  6
         \       \ↆ
          7       9
         / \     /
       -2   11  10
      ↆ/
      8 
      ----------------
         Top element
      8  4  2  1 3  6  9 
      ----------------
         Sum : 33
    */
    tree.topViewNodeSum();
}
main();

Output

 Sum : 33
#  Python 3 program for
#  Sum of nodes in top view of binary tree efficiently
#  Using Map
class TreeNode :
    #  Data value
    #  Indicates left and right subtree
    def __init__(self, data) :
        self.data = data
        self.left = None
        self.right = None
    

class BinaryTree :
    def __init__(self) :
        self.root = None
    
    def findTopNode(self, node, record, distance, level) :
        if (node != None) :
            if (not(distance in record.keys())) :
                #  Get top view element
                record[distance] = node.data
            
            #  Visit left subtree
            self.findTopNode(node.left, 
                             record, distance - 1, level + 1)
            #  Visit right subtree
            self.findTopNode(node.right, 
                             record, distance + 1, level + 1)
        
    
    def topViewNodeSum(self) :
        if (self.root != None) :
            #  Use to collect elements of top view
            record = dict()
            self.findTopNode(self.root, record, 0, 0)
            sum = 0
            for key, value in record.items() :
                sum += value
            
            #  Display calculated result
            print(" Sum : ", sum)
        
    

def main() :
    tree = BinaryTree()
    #     Make A Binary Tree
    #     -----------------------
    #          1
    #         /  \
    #        2    3
    #       /    /  \
    #      4    5    6
    #       \         \
    #        7         9
    #       / \       /
    #     -2   11    10
    #     /
    #    8 
    #  Add Binary tree nodes
    tree.root = TreeNode(1)
    tree.root.left = TreeNode(2)
    tree.root.right = TreeNode(3)
    tree.root.right.right = TreeNode(6)
    tree.root.right.right.right = TreeNode(9)
    tree.root.right.left = TreeNode(5)
    tree.root.left.left = TreeNode(4)
    tree.root.left.left.right = TreeNode(7)
    tree.root.left.left.right.left = TreeNode(-2)
    tree.root.left.left.right.left.left = TreeNode(8)
    tree.root.left.left.right.right = TreeNode(11)
    tree.root.right.right.right.left = TreeNode(10)
    #        ↆ
    #        1
    #      ↆ/ \ↆ
    #      2   3
    #    ↆ/    /\ↆ
    #    4    5  6
    #     \       \ↆ
    #      7       9
    #     / \     /
    #   -2   11  10
    #  ↆ/
    #  8 
    #  ----------------
    #     Top element
    #  8  4  2  1 3  6  9 
    #  ----------------
    #     Sum : 33
    tree.topViewNodeSum()

if __name__ == "__main__": main()

Output

 Sum :  33
#  Ruby program for
#  Sum of nodes in top view of binary tree efficiently
#  Using Map
class TreeNode 
    # Define the accessor and reader of class TreeNode
    attr_reader :data, :left, :right
    attr_accessor :data, :left, :right
    #  Data value
    #  Indicates left and right subtree
    def initialize(data) 
        self.data = data
        self.left = nil
        self.right = nil
    end

end

class BinaryTree 
    # Define the accessor and reader of class BinaryTree
    attr_reader :root
    attr_accessor :root
    def initialize() 
        self.root = nil
    end

    def findTopNode(node, record, distance, level) 
        if (node != nil) 
            if (!record.key?(distance)) 
                #  Get top view element
                record[distance] = node.data
            end

            #  Visit left subtree
            self.findTopNode(node.left, 
                             record, distance - 1, level + 1)
            #  Visit right subtree
            self.findTopNode(node.right, 
                             record, distance + 1, level + 1)
        end

    end

    def topViewNodeSum() 
        if (self.root != nil) 
            #  Use to collect elements of top view
            record = Hash.new()
            self.findTopNode(self.root, record, 0, 0)
            sum = 0
            #  Sum top view nodes
            record.each { | key, value | sum += value
            }
            #  Display calculated result
            print(" Sum : ", sum, "\n")
        end

    end

end

def main() 
    tree = BinaryTree.new()
    #     Make A Binary Tree
    #     -----------------------
    #          1
    #         /  \
    #        2    3
    #       /    /  \
    #      4    5    6
    #       \         \
    #        7         9
    #       / \       /
    #     -2   11    10
    #     /
    #    8
    #  Add Binary tree nodes
    tree.root = TreeNode.new(1)
    tree.root.left = TreeNode.new(2)
    tree.root.right = TreeNode.new(3)
    tree.root.right.right = TreeNode.new(6)
    tree.root.right.right.right = TreeNode.new(9)
    tree.root.right.left = TreeNode.new(5)
    tree.root.left.left = TreeNode.new(4)
    tree.root.left.left.right = TreeNode.new(7)
    tree.root.left.left.right.left = TreeNode.new(-2)
    tree.root.left.left.right.left.left = TreeNode.new(8)
    tree.root.left.left.right.right = TreeNode.new(11)
    tree.root.right.right.right.left = TreeNode.new(10)
    #        ↆ
    #        1
    #      ↆ/ \ↆ
    #      2   3
    #    ↆ/    /\ↆ
    #    4    5  6
    #     \       \ↆ
    #      7       9
    #     / \     /
    #   -2   11  10
    #  ↆ/
    #  8 
    #  ----------------
    #     Top element
    #  8  4  2  1 3  6  9 
    #  ----------------
    #     Sum : 33
    tree.topViewNodeSum()
end

main()

Output

 Sum : 33

import scala.collection.mutable._;
// Scala program for
// Sum of nodes in top view of binary tree efficiently
// Using Map
class TreeNode(
    // Data value
    var data: Int,
        // Indicates left and right subtree
        var left: TreeNode,
            var right: TreeNode)
{
    def this(data: Int)
    {
        this(data, null, null);
    }
}
class BinaryTree(var root: TreeNode)
{
    def this()
    {
        this(null);
    }
    def findTopNode(node: TreeNode, 
                    record: HashMap[Int, Int], 
                    distance: Int, 
                    level: Int): Unit = {
        if (node != null)
        {
            if (!record.contains(distance))
            {
                // Get top view element
                record.addOne(distance, node.data);
            }
            // Visit left subtree
            findTopNode(node.left, 
                        record, distance - 1, level + 1);
            // Visit right subtree
            findTopNode(node.right, 
                        record, distance + 1, level + 1);
        }
    }
    def topViewNodeSum(): Unit = {
        if (this.root != null)
        {
            // Use to collect elements of top view
            var record: HashMap[Int, Int] = new HashMap[Int, Int]();
            findTopNode(this.root, record, 0, 0);
            var sum: Int = 0;
            // Sum top view nodes
            for ((key, value) <- record)
            {
                sum += value;
            }
            // Display calculated result
            println(" Sum : " + sum);
        }
    }
}
object Main
{
    def main(args: Array[String]): Unit = {
        var tree: BinaryTree = new BinaryTree();
        /* 
             Make A Binary Tree
             -----------------------
                  1
                 /  \
                2    3
               /    /  \
              4    5    6
               \         \
                7         9
               / \       /
             -2   11    10
             /
            8              
              
        */
        // Add Binary tree nodes
        tree.root = new TreeNode(1);
        tree.root.left = new TreeNode(2);
        tree.root.right = new TreeNode(3);
        tree.root.right.right = new TreeNode(6);
        tree.root.right.right.right = new TreeNode(9);
        tree.root.right.left = new TreeNode(5);
        tree.root.left.left = new TreeNode(4);
        tree.root.left.left.right = new TreeNode(7);
        tree.root.left.left.right.left = new TreeNode(-2);
        tree.root.left.left.right.left.left = new TreeNode(8);
        tree.root.left.left.right.right = new TreeNode(11);
        tree.root.right.right.right.left = new TreeNode(10);
        /*
                ↆ
                1
              ↆ/ \ↆ
              2   3
            ↆ/    /\ↆ
            4    5  6
             \       \ↆ
              7       9
             / \     /
           -2   11  10
          ↆ/
          8 
          ----------------
             Top element
          8  4  2  1 3  6  9 
          ----------------
             Sum : 33
        */
        tree.topViewNodeSum();
    }
}

Output

 Sum : 33
import Foundation;
// Swift 4 program for
// Sum of nodes in top view of binary tree efficiently
// Using Map
class TreeNode
{
    // Data value
    var data: Int;
    // Indicates left and right subtree
    var left: TreeNode? ;
    var right: TreeNode? ;
    init(_ data: Int)
    {
        self.data = data;
        self.left = nil;
        self.right = nil;
    }
}
class BinaryTree
{
    var root: TreeNode? ;
    init()
    {
        self.root = nil;
    }
    func findTopNode(_ node: TreeNode? , 
                     _ record : inout[Int:Int], 
                     _ distance: Int, 
                     _ level: Int)
    {
        if (node  != nil)
        {
            if (!record.keys.contains(distance))
            {
                // Get top view element
                record[distance] = node!.data;
            }
            // Visit left subtree
            self.findTopNode(node!.left, &record, distance - 1, level + 1);
            // Visit right subtree
            self.findTopNode(node!.right, &record, distance + 1, level + 1);
        }
    }
    func topViewNodeSum()
    {
        if (self.root  != nil)
        {
            // Use to collect elements of top view
            var record: [Int:Int] = [Int:Int]();
            self.findTopNode(self.root, &record, 0, 0);
            var sum: Int = 0;
            // Sum top view nodes
            for (_, value) in record
            {
                sum += value;
            }
            // Display calculated result
            print(" Sum : ", sum);
        }
    }
}
func main()
{
    let tree: BinaryTree = BinaryTree();
    /* 
         Make A Binary Tree
         -----------------------
              1
             /  \
            2    3
           /    /  \
          4    5    6
           \         \
            7         9
           / \       /
         -2   11    10
         /
        8           
    */
    // Add Binary tree nodes
    tree.root = TreeNode(1);
    tree.root!.left = TreeNode(2);
    tree.root!.right = TreeNode(3);
    tree.root!.right!.right = TreeNode(6);
    tree.root!.right!.right!.right = TreeNode(9);
    tree.root!.right!.left = TreeNode(5);
    tree.root!.left!.left = TreeNode(4);
    tree.root!.left!.left!.right = TreeNode(7);
    tree.root!.left!.left!.right!.left = TreeNode(-2);
    tree.root!.left!.left!.right!.left!.left = TreeNode(8);
    tree.root!.left!.left!.right!.right = TreeNode(11);
    tree.root!.right!.right!.right!.left = TreeNode(10);
    /*
            ↆ
            1
          ↆ/ \ↆ
          2   3
        ↆ/    /\ↆ
        4    5  6
         \       \ↆ
          7       9
         / \     /
       -2   11  10
      ↆ/
      8 
      ----------------
         Top element
      8  4  2  1 3  6  9 
      ----------------
         Sum : 33
    */
    tree.topViewNodeSum();
}
main();

Output

 Sum :  33
// Kotlin program for
// Sum of nodes in top view of binary tree efficiently
// Using Map
class TreeNode
{
    // Data value
    var data: Int;
    // Indicates left and right subtree
    var left: TreeNode ? ;
    var right: TreeNode ? ;
    constructor(data: Int)
    {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}
class BinaryTree
{
    var root: TreeNode ? ;
    constructor()
    {
        this.root = null;
    }
    fun findTopNode(node: TreeNode ? , 
                    record : HashMap < Int, Int >  , 
                    distance : Int, level: Int): Unit
    {
        if (node != null)
        {
            if (!record.containsKey(distance))
            {
                // Get top view element
                record.put(distance, node.data);
            }
            // Visit left subtree
            this.findTopNode(node.left, record, distance - 1, level + 1);
            // Visit right subtree
            this.findTopNode(node.right, record, distance + 1, level + 1);
        }
    }
    fun topViewNodeSum(): Unit
    {
        if (this.root != null)
        {
            // Use to collect elements of top view
            var record: HashMap < Int, Int > = HashMap < Int, Int > ();
            this.findTopNode(this.root, record, 0, 0);
            var sum: Int = 0;
            // Sum top view nodes
            for ((_, value) in record)
            {
                sum += value;
            }
            // Display calculated result
            println(" Sum : " + sum);
        }
    }
}
fun main(args: Array < String > ): Unit
{
    val tree: BinaryTree = BinaryTree();
    /* 
         Make A Binary Tree
         -----------------------
              1
             /  \
            2    3
           /    /  \
          4    5    6
           \         \
            7         9
           / \       /
         -2   11    10
         /
        8 
    */
    // Add Binary tree nodes
    tree.root = TreeNode(1);
    tree.root?.left = TreeNode(2);
    tree.root?.right = TreeNode(3);
    tree.root?.right?.right = TreeNode(6);
    tree.root?.right?.right?.right = TreeNode(9);
    tree.root?.right?.left = TreeNode(5);
    tree.root?.left?.left = TreeNode(4);
    tree.root?.left?.left?.right = TreeNode(7);
    tree.root?.left?.left?.right?.left = TreeNode(-2);
    tree.root?.left?.left?.right?.left?.left = TreeNode(8);
    tree.root?.left?.left?.right?.right = TreeNode(11);
    tree.root?.right?.right?.right?.left = TreeNode(10);
    /*
            ↆ
            1
          ↆ/ \ↆ
          2   3
        ↆ/    /\ↆ
        4    5  6
         \       \ↆ
          7       9
         / \     /
       -2   11  10
      ↆ/
      8 
      ----------------
         Top element
      8  4  2  1 3  6  9 
      ----------------
         Sum : 33
    */
    tree.topViewNodeSum();
}

Output

 Sum : 33
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