Sum of nodes in bottom view of Binary Tree

sum of bottom view of binary tree

Here given code implementation process.

import java.util.HashMap;
// Java program for
// Sum of nodes in bottom view of Binary Tree
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;
	}
}
class Result
{
	public int value;
	public int level;
	public Result(int value, int level)
	{
		this.value = value;
		this.level = level;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		this.root = null;
	}
	public void findBottomNode(TreeNode node, 
                                HashMap < Integer, Result > record, 
                                int distance, int level)
	{
		if (node != null)
		{
			if (!record.containsKey(distance))
			{
				// Add new node in bottom view
				record.put(distance, new Result(node.data, level));
			}
			else if (record.get(distance).level < level)
			{
				// Update bottom view node
				record.get(distance).level = level;
				// Update node value
				record.get(distance).value = node.data;
			}
			// Visit left subtree
			findBottomNode(node.left, record, distance - 1, level + 1);
			// Visit right subtree
			findBottomNode(node.right, record, distance + 1, level + 1);
		}
	}
	public void bottomNodeSum()
	{
		if (this.root != null)
		{
			HashMap < Integer, Result > record = 
              new HashMap < Integer, Result > ();
			findBottomNode(this.root, record, 0, 0);
			int sum = 0;
			// Sum bottom view nodes
			for (int info: record.keySet())
			{
				sum += record.get(info).value;
			}
			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
      */
		// 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.right = new TreeNode(11);
		tree.root.right.right.right.left = new TreeNode(10);
		/*
		  --------------------
		        1
		       /  \
		      2    3
		     /    /  \
		    4    5    6
		     \         \
		      7         9
		     / \       /
		   -2   11    10
		  --------------------
		   Bottom element
		   -2 7 11 3 10 9 
		   ----------------
		     Sum : 38
		*/
		tree.bottomNodeSum();
	}
}

Output

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

using namespace std;
// C++ program for
// Sum of nodes in bottom view of Binary Tree
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 Result
{
    public: int value;
    int level;
    Result(int value, int level)
    {
        this->value = value;
        this->level = level;
    }
};
class BinaryTree
{
    public: TreeNode *root;
    BinaryTree()
    {
        this->root = NULL;
    }
    void findBottomNode(TreeNode *node, 
                        unordered_map < int, Result *> &record, 
                        int distance, int level)
    {
        if (node != NULL)
        {
            if (record.find(distance) == record.end())
            {
                // Add new node in bottom view
                record[distance] = new Result(node->data, level);
            }
            else if (record[distance]->level < level)
            {
                // Update bottom view node
                record[distance]->level = level;
                // Update node value
                record[distance]->value = node->data;
            }
            // Visit left subtree
            this->findBottomNode(node->left, record, distance - 1, level + 1);
            // Visit right subtree
            this->findBottomNode(node->right, record, distance + 1, level + 1);
        }
    }
    void bottomNodeSum()
    {
        if (this->root != NULL)
        {
            unordered_map < int, Result *> record;
            this->findBottomNode(this->root, record, 0, 0);
            int sum = 0;
            // Sum bottom view nodes
            for (auto &info: record)
            {
                sum += record[info.first]->value;
            }
            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
          
    */
    // 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->right = new TreeNode(11);
    tree->root->right->right->right->left = new TreeNode(10);
    /*
      --------------------
            1
           /  \
          2    3
         /    /  \
        4    5    6
         \         \
          7         9
         / \       /
       -2   11    10
      --------------------
       Bottom element
       -2 7 11 3 10 9 
       ----------------
         Sum : 38
    */
    tree->bottomNodeSum();
    return 0;
}

Output

 Sum : 38
package main
import "fmt"
// Go program for
// Sum of nodes in bottom view of Binary Tree
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 Result struct {
	value int
	level int
}
func getResult(value int, level int) * Result {
	var me *Result = &Result {}
	me.value = value
	me.level = level
	return me
}
type BinaryTree struct {
	root * TreeNode
}
func getBinaryTree() * BinaryTree {
	var me *BinaryTree = &BinaryTree {}
	me.root = nil
	return me
}
func(this BinaryTree) findBottomNode(node * TreeNode, 
	record map[int] *Result, distance int, level int) {
	if node != nil {
		if _, found := record[distance] ; !found {
			// Add new node in bottom view
			record[distance] = getResult(node.data, level)
		} else if record[distance].level < level {
			// Update bottom view node
			record[distance].level = level
			// Update node value
			record[distance].value = node.data
		}
		// Visit left subtree
		this.findBottomNode(node.left, record, distance - 1, level + 1)
		// Visit right subtree
		this.findBottomNode(node.right, record, distance + 1, level + 1)
	}
}
func(this BinaryTree) bottomNodeSum() {
	if this.root != nil {
		var record = make(map[int] *Result)
		this.findBottomNode(this.root, record, 0, 0)
		var sum int = 0
		// Sum bottom view nodes
		for _, node := range record {
			sum += node.value
		}
		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
	      
	*/
	// 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.right = getTreeNode(11)
	tree.root.right.right.right.left = getTreeNode(10)
	/*
	  --------------------
	        1
	       /  \
	      2    3
	     /    /  \
	    4    5    6
	     \         \
	      7         9
	     / \       /
	   -2   11    10
	  --------------------
	   Bottom element
	   -2 7 11 3 10 9 
	   ----------------
	     Sum : 38
	*/
	tree.bottomNodeSum()
}

Output

 Sum : 38
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp program for
// Sum of nodes in bottom view of Binary Tree
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 Result
{
	public int value;
	public int level;
	public Result(int value, int level)
	{
		this.value = value;
		this.level = level;
	}
}
public class BinaryTree
{
	public TreeNode root;
	public BinaryTree()
	{
		this.root = null;
	}
	public void findBottomNode(TreeNode node, 
                                Dictionary < int, Result > record, 
                                int distance, int level)
	{
		if (node != null)
		{
			if (!record.ContainsKey(distance))
			{
				// Add new node in bottom view
				record.Add(distance, new Result(node.data, level));
			}
			else if (record[distance].level < level)
			{
				// Update bottom view node
				record[distance].level = level;
				// Update node value
				record[distance].value = node.data;
			}
			// Visit left subtree
			this.findBottomNode(node.left, record, distance - 1, level + 1);
			// Visit right subtree
			this.findBottomNode(node.right, record, distance + 1, level + 1);
		}
	}
	public void bottomNodeSum()
	{
		if (this.root != null)
		{
			Dictionary < int, Result > record = 
              new Dictionary < int, Result > ();
			this.findBottomNode(this.root, record, 0, 0);
			int sum = 0;
			// Sum bottom view nodes
			foreach(KeyValuePair < int, Result > info in record)
			{
				sum += info.Value.value;
			}
			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
		      
		*/
		// 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.right = new TreeNode(11);
		tree.root.right.right.right.left = new TreeNode(10);
		/*
		  --------------------
		        1
		       /  \
		      2    3
		     /    /  \
		    4    5    6
		     \         \
		      7         9
		     / \       /
		   -2   11    10
		  --------------------
		   Bottom element
		   -2 7 11 3 10 9 
		   ----------------
		     Sum : 38
		*/
		tree.bottomNodeSum();
	}
}

Output

 Sum : 38
<?php
// Php program for
// Sum of nodes in bottom view of Binary Tree
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 Result
{
	public $value;
	public $level;
	public	function __construct($value, $level)
	{
		$this->value = $value;
		$this->level = $level;
	}
}
class BinaryTree
{
	public $root;
	public	function __construct()
	{
		$this->root = NULL;
	}
	public	function findBottomNode($node, &$record, $distance, $level)
	{
		if ($node != NULL)
		{
			if (!array_key_exists($distance, $record))
			{
				// Add new node in bottom view
				$record[$distance] = new Result($node->data, $level);
			}
			else if ($record[$distance]->level < $level)
			{
				// Update bottom view node
				$record[$distance]->level = $level;
				// Update node value
				$record[$distance]->value = $node->data;
			}
			// Visit left subtree
			$this->findBottomNode($node->left, $record, 
                                  $distance - 1, $level + 1);
			// Visit right subtree
			$this->findBottomNode($node->right, $record, 
                                  $distance + 1, $level + 1);
		}
	}
	public	function bottomNodeSum()
	{
		if ($this->root != NULL)
		{
			$record = array();
			$this->findBottomNode($this->root, $record, 0, 0);
			$sum = 0;
			// Sum bottom view nodes
			foreach($record as $key => $value)
			{
				$sum += $value->value;
			}
			echo(" Sum : ".$sum."\n");
		}
	}
}

function main()
{
	$tree = new BinaryTree();
	/*
	    Make A Binary Tree
	    ---------------------
	      1
	     /  \
	    2    3
	   /    /  \
	  4    5    6
	   \         \
	    7         9
	   / \       /
	 -2   11    10
	      
	*/
	// 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->right = new TreeNode(11);
	$tree->root->right->right->right->left = new TreeNode(10);
	/*
	  --------------------
	        1
	       /  \
	      2    3
	     /    /  \
	    4    5    6
	     \         \
	      7         9
	     / \       /
	   -2   11    10
	  --------------------
	   Bottom element
	   -2 7 11 3 10 9 
	   ----------------
	     Sum : 38
	*/
	$tree->bottomNodeSum();
}
main();

Output

 Sum : 38
// Node JS program for
// Sum of nodes in bottom view of Binary Tree
class TreeNode
{
	constructor(data)
	{
		this.data = data;
		this.left = null;
		this.right = null;
	}
}
class Result
{
	constructor(value, level)
	{
		this.value = value;
		this.level = level;
	}
}
class BinaryTree
{
	constructor()
	{
		this.root = null;
	}
	findBottomNode(node, record, distance, level)
	{
		if (node != null)
		{
			if (!record.has(distance))
			{
				// Add new node in bottom view
				record.set(distance, new Result(node.data, level));
			}
			else if (record.get(distance).level < level)
			{
				// Update bottom view node
				record.get(distance).level = level;
				// Update node value
				record.get(distance).value = node.data;
			}
			// Visit left subtree
			this.findBottomNode(node.left, 
                                record, 
                                distance - 1, 
                                level + 1);
			// Visit right subtree
			this.findBottomNode(node.right, 
                                record, 
                                distance + 1, 
                                level + 1);
		}
	}
	bottomNodeSum()
	{
		if (this.root != null)
		{
			var record = new Map();
			this.findBottomNode(this.root, record, 0, 0);
			var sum = 0;
			// Sum bottom view nodes
			for (let [key, node] of record)
			{
				sum += node.value;
			}
			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
	      
	*/
	// 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.right = new TreeNode(11);
	tree.root.right.right.right.left = new TreeNode(10);
	/*
	  --------------------
	        1
	       /  \
	      2    3
	     /    /  \
	    4    5    6
	     \         \
	      7         9
	     / \       /
	   -2   11    10
	  --------------------
	   Bottom element
	   -2 7 11 3 10 9 
	   ----------------
	     Sum : 38
	*/
	tree.bottomNodeSum();
}
main();

Output

 Sum : 38
#  Python 3 program for
#  Sum of nodes in bottom view of Binary Tree
class TreeNode :
	#  Data value
	#  Indicates left and right subtree
	def __init__(self, data) :
		self.data = data
		self.left = None
		self.right = None
	

class Result :
	def __init__(self, value, level) :
		self.value = value
		self.level = level
	

class BinaryTree :
	def __init__(self) :
		self.root = None
	
	def findBottomNode(self, node, record, distance, level) :
		if (node != None) :
			if (not(distance in record.keys())) :
				#  Add new node in bottom view
				record[distance] = Result(node.data, level)
			elif (record.get(distance).level < level) :
				#  Update bottom view node
				record.get(distance).level = level
				#  Update node value
				record.get(distance).value = node.data
			
			#  Visit left subtree
			self.findBottomNode(node.left, record, distance - 1, level + 1)
			#  Visit right subtree
			self.findBottomNode(node.right, record, distance + 1, level + 1)
		
	
	def bottomNodeSum(self) :
		if (self.root != None) :
			record = dict()
			self.findBottomNode(self.root, record, 0, 0)
			sum = 0
			for key, node in record.items() :
				sum += node.value
			
			print(" Sum : ", sum)
		
	

def main() :
	tree = BinaryTree()
	#    Make A Binary Tree
	#    ---------------------
	#      1
	#     /  \
	#    2    3
	#   /    /  \
	#  4    5    6
	#   \         \
	#    7         9
	#   / \       /
	# -2   11    10
	#  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.right = TreeNode(11)
	tree.root.right.right.right.left = TreeNode(10)
	#  --------------------
	#        1
	#       /  \
	#      2    3
	#     /    /  \
	#    4    5    6
	#     \         \
	#      7         9
	#     / \       /
	#   -2   11    10
	#  --------------------
	#   Bottom element
	#   -2 7 11 3 10 9 
	#   ----------------
	#     Sum : 38
	tree.bottomNodeSum()

if __name__ == "__main__": main()

Output

 Sum :  38
#  Ruby program for
#  Sum of nodes in bottom view of Binary Tree
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 Result 
	# Define the accessor and reader of class Result
	attr_reader :value, :level
	attr_accessor :value, :level
	def initialize(value, level) 
		self.value = value
		self.level = level
	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 findBottomNode(node, record, distance, level) 
		if (node != nil) 
			if (!record.key?(distance)) 
				#  Add new node in bottom view
				record[distance] = Result.new(node.data, level)
			elsif (record[distance].level < level) 
				#  Update bottom view node
				record[distance].level = level
				#  Update node value
				record[distance].value = node.data
			end

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

	end

	def bottomNodeSum() 
		if (self.root != nil) 
			record = Hash.new()
			self.findBottomNode(self.root, record, 0, 0)
			sum = 0
			#  Sum bottom view nodes
			record.each { | key, node | sum += node.value
			}
			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
	#  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.right = TreeNode.new(11)
	tree.root.right.right.right.left = TreeNode.new(10)
	#  --------------------
	#        1
	#       /  \
	#      2    3
	#     /    /  \
	#    4    5    6
	#     \         \
	#      7         9
	#     / \       /
	#   -2   11    10
	#  --------------------
	#   Bottom element
	#   -2 7 11 3 10 9 
	#   ----------------
	#     Sum : 38
	tree.bottomNodeSum()
end

main()

Output

 Sum : 38

import scala.collection.mutable._;
// Scala program for
// Sum of nodes in bottom view of Binary Tree
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 Result(var value: Int,
	var level: Int);
class BinaryTree(var root: TreeNode)
{
	def this()
	{
		this(null);
	}
	def findBottomNode(node: TreeNode, 
                       record: HashMap[Int, Result], 
      distance: Int, level: Int): Unit = {
		if (node != null)
		{
			if (!record.contains(distance))
			{
				// Add new node in bottom view
				record.addOne(distance, new Result(node.data, level));
			}
			else if (record.get(distance).get.level < level)
			{
				// Update bottom view node
				record.get(distance).get.level = level;
				// Update node value
				record.get(distance).get.value = node.data;
			}
			// Visit left subtree
			findBottomNode(node.left, record, distance - 1, level + 1);
			// Visit right subtree
			findBottomNode(node.right, record, distance + 1, level + 1);
		}
	}
	def bottomNodeSum(): Unit = {
		if (this.root != null)
		{
			var record: HashMap[Int, Result] = new HashMap[Int, Result]();
			findBottomNode(this.root, record, 0, 0);
			var sum: Int = 0;
			// Sum bottom view nodes
            for ((key, node) <- record)
            {
                sum += node.value;
            } 
			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
		      
		*/
		// 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.right = new TreeNode(11);
		tree.root.right.right.right.left = new TreeNode(10);
		/*
		  --------------------
		        1
		       /  \
		      2    3
		     /    /  \
		    4    5    6
		     \         \
		      7         9
		     / \       /
		   -2   11    10
		  --------------------
		   Bottom element
		   -2 7 11 3 10 9 
		   ----------------
		     Sum : 38
		*/
		tree.bottomNodeSum();
	}
}

Output

 Sum : 38
import Foundation;
// Swift 4 program for
// Sum of nodes in bottom view of Binary Tree
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 Result
{
	var value: Int;
	var level: Int;
	init(_ value: Int, _ level: Int)
	{
		self.value = value;
		self.level = level;
	}
}
class BinaryTree
{
	var root: TreeNode? ;
	init()
	{
		self.root = nil;
	}
	func findBottomNode(_ node: TreeNode? , 
                        _ record : inout[Int:Result], 
      _ distance: Int, _ level: Int)
	{
		if (node  != nil)
		{
			if (!record.keys.contains(distance))
			{
				// Add new node in bottom view
				record[distance] = Result(node!.data, level);
			}
			else if (record[distance]!.level < level)
			{
				// Update bottom view node
				record[distance]!.level = level;
				// Update node value
				record[distance]!.value = node!.data;
			}
			// Visit left subtree
			self.findBottomNode(node!.left, &record, distance - 1, level + 1);
			// Visit right subtree
			self.findBottomNode(node!.right, &record, distance + 1, level + 1);
		}
	}
	func bottomNodeSum()
	{
		if (self.root  != nil)
		{
			var record: [Int:Result] = [Int:Result]();
			self.findBottomNode(self.root, &record, 0, 0);
			var sum: Int = 0;
			// Sum bottom view nodes
			for (_, node) in record
			{
				sum += node.value;
			}
			print(" Sum : ", sum);
		}
	}
}
func main()
{
	let tree: BinaryTree = BinaryTree();
	/*
	    Make A Binary Tree
	    ---------------------
	      1
	     /  \
	    2    3
	   /    /  \
	  4    5    6
	   \         \
	    7         9
	   / \       /
	 -2   11    10
	      
	*/
	// 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!.right = TreeNode(11);
	tree.root!.right!.right!.right!.left = TreeNode(10);
	/*
	  --------------------
	        1
	       /  \
	      2    3
	     /    /  \
	    4    5    6
	     \         \
	      7         9
	     / \       /
	   -2   11    10
	  --------------------
	   Bottom element
	   -2 7 11 3 10 9 
	   ----------------
	     Sum : 38
	*/
	tree.bottomNodeSum();
}
main();

Output

 Sum :  38
// Kotlin program for
// Sum of nodes in bottom view of Binary Tree
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 Result
{
	var value: Int;
	var level: Int;
	constructor(value: Int, level: Int)
	{
		this.value = value;
		this.level = level;
	}
}
class BinaryTree
{
	var root: TreeNode ? ;
	constructor()
	{
		this.root = null;
	}
	fun findBottomNode(node: TreeNode ? , 
                       record : HashMap < Int, Result > , 
                       distance : Int, level: Int): Unit
	{
		if (node != null)
		{
			if (!record.containsKey(distance))
			{
				// Add new node in bottom view
				record.put(distance, Result(node.data, level));
			}
			else if (record.getValue(distance).level < level)
			{
				// Update bottom view node
				record.getValue(distance).level = level;
				// Update node value
				record.getValue(distance).value = node.data;
			}
			// Visit left subtree
			this.findBottomNode(node.left, 
                                record, distance - 1, level + 1);
			// Visit right subtree
			this.findBottomNode(node.right, 
                                record, distance + 1, level + 1);
		}
	}
	fun bottomNodeSum(): Unit
	{
		if (this.root != null)
		{
			var record: HashMap < Int, Result > = 
              HashMap < Int, Result > ();
			this.findBottomNode(this.root, record, 0, 0);
			var sum: Int = 0;
			// Sum bottom view nodes
			for ((_, node) in record)
			{
				sum += node.value;
			}
			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
	      
	*/
	// 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?.right = TreeNode(11);
	tree.root?.right?.right?.right?.left = TreeNode(10);
	/*
	  --------------------
	        1
	       /  \
	      2    3
	     /    /  \
	    4    5    6
	     \         \
	      7         9
	     / \       /
	   -2   11    10
	  --------------------
	   Bottom element
	   -2 7 11 3 10 9 
	   ----------------
	     Sum : 38
	*/
	tree.bottomNodeSum();
}

Output

 Sum : 38


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




© 2021, kalkicode.com, All rights reserved