Vertical sum of given binary tree efficiently

Here given code implementation process.
import java.util.HashMap;
// Java Program
// Vertical sum of given binary tree efficiently
// Binary Tree node
class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
this.root = null;
}
public void findVerticalSum(TreeNode node,
int distance,
HashMap < Integer, Integer > record)
{
if (node != null)
{
if (record.containsKey(distance))
{
// Update new vertical value
record.put(distance, record.get(distance) + node.data);
}
else
{
// Add new vertical distance and value
record.put(distance, node.data);
}
// Visit left and right subtree recursively and find vertical sum
findVerticalSum(node.left, distance - 1, record);
findVerticalSum(node.right, distance + 1, record);
}
}
public void verticalSum()
{
if (this.root == null)
{
return;
}
// Use to collect vertical sum result
HashMap < Integer, Integer > record =
new HashMap < Integer, Integer > ();
this.findVerticalSum(this.root, 0, record);
// Use to collect range of print data from left to right
int min = Integer.MAX_VALUE;
int max = Integer.MIN_VALUE;
// Find left and right boundary to display result
for (int key: record.keySet())
{
if (min > key)
{
min = key;
}
if (max < key)
{
max = key;
}
}
// Display the resultant value from left to right order
while (min <= max)
{
System.out.print(" " + record.get(min));
min++;
}
}
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
/* Binary Tree
-----------------------
4
/ \
3 10
/ / \
2 9 11
/ \
5 12
/ \
8 7
*/
// Add node in binary tree
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(3);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(10);
tree.root.right.right = new TreeNode(11);
tree.root.right.left = new TreeNode(9);
tree.root.right.left.left = new TreeNode(5);
tree.root.right.left.right = new TreeNode(12);
tree.root.right.left.right.right = new TreeNode(7);
tree.root.right.left.right.left = new TreeNode(8);
tree.verticalSum();
}
}
Output
2 8 21 22 18
// Include header file
#include <iostream>
#include <unordered_map>
#include <limits.h>
using namespace std;
// C++ Program
// Vertical sum of given binary tree efficiently
// Binary Tree node
class TreeNode
{
public:
int data;
TreeNode *left;
TreeNode *right;
TreeNode(int data)
{
// Set node value
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
class BinaryTree
{
public:
TreeNode *root;
BinaryTree()
{
this->root = NULL;
}
void findVerticalSum(TreeNode *node,
int distance,
unordered_map < int, int > &record)
{
if (node != NULL)
{
if (record.find(distance) != record.end())
{
// Update new vertical value
record[distance] = record[distance] + node->data;
}
else
{
// Add new vertical distance and value
record[distance] = node->data;
}
// Visit left and right subtree recursively and find vertical sum
this->findVerticalSum(node->left, distance - 1, record);
this->findVerticalSum(node->right, distance + 1, record);
}
}
void verticalSum()
{
if (this->root == NULL)
{
return;
}
// Use to collect vertical sum result
unordered_map < int, int > record;
this->findVerticalSum(this->root, 0, record);
// Use to collect range of print data from left to right
int min = INT_MAX;
int max = INT_MIN;
// Find left and right boundary to display result
for (auto &key: record)
{
if (min > key.first)
{
min = key.first;
}
if (max < key.first)
{
max = key.first;
}
}
// Display the resultant value from left to right order
while (min <= max)
{
cout << " " << record[min];
min++;
}
}
};
int main()
{
BinaryTree *tree = new BinaryTree();
/*
Binary Tree
-----------------------
4
/ \
3 10
/ / \
2 9 11
/ \
5 12
/ \
8 7
*/
// Add node in binary tree
tree->root = new TreeNode(4);
tree->root->left = new TreeNode(3);
tree->root->left->left = new TreeNode(2);
tree->root->right = new TreeNode(10);
tree->root->right->right = new TreeNode(11);
tree->root->right->left = new TreeNode(9);
tree->root->right->left->left = new TreeNode(5);
tree->root->right->left->right = new TreeNode(12);
tree->root->right->left->right->right = new TreeNode(7);
tree->root->right->left->right->left = new TreeNode(8);
tree->verticalSum();
return 0;
}
Output
2 8 21 22 18
// Include namespace system
using System;
using System.Collections.Generic;
// Csharp Program
// Vertical sum of given binary tree efficiently
// Binary Tree node
public class TreeNode
{
public int data;
public TreeNode left;
public TreeNode right;
public TreeNode(int data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
public class BinaryTree
{
public TreeNode root;
public BinaryTree()
{
this.root = null;
}
public void findVerticalSum(TreeNode node,
int distance,
Dictionary < int, int > record)
{
if (node != null)
{
if (record.ContainsKey(distance))
{
// Update new vertical value
record[distance] = record[distance] + node.data;
}
else
{
// Add new vertical distance and value
record.Add(distance, node.data);
}
// Visit left and right subtree recursively and find vertical sum
this.findVerticalSum(node.left, distance - 1, record);
this.findVerticalSum(node.right, distance + 1, record);
}
}
public void verticalSum()
{
if (this.root == null)
{
return;
}
// Use to collect vertical sum result
Dictionary < int, int > record = new Dictionary < int, int > ();
this.findVerticalSum(this.root, 0, record);
// Use to collect range of print data from left to right
int min = int.MaxValue;
int max = int.MinValue;
// Find left and right boundary to display result
foreach(KeyValuePair < int, int > info in record)
{
if (min > info.Key)
{
min = info.Key;
}
if (max < info.Key)
{
max = info.Key;
}
}
// Display the resultant value from left to right order
while (min <= max)
{
Console.Write(" " + record[min]);
min++;
}
}
public static void Main(String[] args)
{
BinaryTree tree = new BinaryTree();
/*
Binary Tree
-----------------------
4
/ \
3 10
/ / \
2 9 11
/ \
5 12
/ \
8 7
*/
// Add node in binary tree
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(3);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(10);
tree.root.right.right = new TreeNode(11);
tree.root.right.left = new TreeNode(9);
tree.root.right.left.left = new TreeNode(5);
tree.root.right.left.right = new TreeNode(12);
tree.root.right.left.right.right = new TreeNode(7);
tree.root.right.left.right.left = new TreeNode(8);
tree.verticalSum();
}
}
Output
2 8 21 22 18
package main
import "math"
import "fmt"
// Go Program
// Vertical sum of given binary tree efficiently
// Binary Tree node
type TreeNode struct {
data int
left * TreeNode
right * TreeNode
}
func getTreeNode(data int) * TreeNode {
var me *TreeNode = &TreeNode {}
// Set node value
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) findVerticalSum(node * TreeNode, distance int, record map[int]int) {
if node != nil {
if _, found := record[distance] ; found {
// Update new vertical value
record[distance] = record[distance] + node.data
} else {
// Add new vertical distance and value
record[distance] = node.data
}
// Visit left and right subtree recursively and find vertical sum
this.findVerticalSum(node.left, distance - 1, record)
this.findVerticalSum(node.right, distance + 1, record)
}
}
func(this BinaryTree) verticalSum() {
if this.root == nil {
return
}
// Use to collect vertical sum result
var record = make(map[int] int)
this.findVerticalSum(this.root, 0, record)
// Use to collect range of print data from left to right
var min int = math.MaxInt64
var max int = math.MinInt64
// Find left and right boundary to display result
for k, _ := range record {
if min > k {
min = k
}
if max < k {
max = k
}
}
// Display the resultant value from left to right order
for (min <= max) {
fmt.Print(" ", record[min])
min++
}
}
func main() {
var tree * BinaryTree = getBinaryTree()
/*
Binary Tree
-----------------------
4
/ \
3 10
/ / \
2 9 11
/ \
5 12
/ \
8 7
*/
// Add node in binary tree
tree.root = getTreeNode(4)
tree.root.left = getTreeNode(3)
tree.root.left.left = getTreeNode(2)
tree.root.right = getTreeNode(10)
tree.root.right.right = getTreeNode(11)
tree.root.right.left = getTreeNode(9)
tree.root.right.left.left = getTreeNode(5)
tree.root.right.left.right = getTreeNode(12)
tree.root.right.left.right.right = getTreeNode(7)
tree.root.right.left.right.left = getTreeNode(8)
tree.verticalSum()
}
Output
2 8 21 22 18
<?php
// Php Program
// Vertical sum of given binary tree efficiently
// Binary Tree node
class TreeNode
{
public $data;
public $left;
public $right;
public function __construct($data)
{
// Set node value
$this->data = $data;
$this->left = NULL;
$this->right = NULL;
}
}
class BinaryTree
{
public $root;
public function __construct()
{
$this->root = NULL;
}
public function findVerticalSum($node, $distance, &$record)
{
if ($node != NULL)
{
if (array_key_exists($distance, $record))
{
// Update new vertical value
$record[$distance] = $record[$distance] + $node->data;
}
else
{
// Add new vertical distance and value
$record[$distance] = $node->data;
}
// Visit left and right subtree recursively and find vertical sum
$this->findVerticalSum($node->left, $distance - 1, $record);
$this->findVerticalSum($node->right, $distance + 1, $record);
}
}
public function verticalSum()
{
if ($this->root == NULL)
{
return;
}
// Use to collect vertical sum result
$record = array();
$this->findVerticalSum($this->root, 0, $record);
// Use to collect range of print data from left to right
$min = PHP_INT_MAX;
$max = -PHP_INT_MAX;
// Find left and right boundary to display result
foreach($record as $key => $value)
{
if ($min > $key)
{
$min = $key;
}
if ($max < $key)
{
$max = $key;
}
}
// Display the resultant value from left to right order
while ($min <= $max)
{
echo(" ".$record[$min]);
$min++;
}
}
}
function main()
{
$tree = new BinaryTree();
/*
Binary Tree
-----------------------
4
/ \
3 10
/ / \
2 9 11
/ \
5 12
/ \
8 7
*/
// Add node in binary tree
$tree->root = new TreeNode(4);
$tree->root->left = new TreeNode(3);
$tree->root->left->left = new TreeNode(2);
$tree->root->right = new TreeNode(10);
$tree->root->right->right = new TreeNode(11);
$tree->root->right->left = new TreeNode(9);
$tree->root->right->left->left = new TreeNode(5);
$tree->root->right->left->right = new TreeNode(12);
$tree->root->right->left->right->right = new TreeNode(7);
$tree->root->right->left->right->left = new TreeNode(8);
$tree->verticalSum();
}
main();
Output
2 8 21 22 18
// Node JS Program
// Vertical sum of given binary tree efficiently
// Binary Tree node
class TreeNode
{
constructor(data)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
constructor()
{
this.root = null;
}
findVerticalSum(node, distance, record)
{
if (node != null)
{
if (record.has(distance))
{
// Update new vertical value
record.set(distance, record.get(distance) + node.data);
}
else
{
// Add new vertical distance and value
record.set(distance, node.data);
}
// Visit left and right subtree recursively and find vertical sum
this.findVerticalSum(node.left, distance - 1, record);
this.findVerticalSum(node.right, distance + 1, record);
}
}
verticalSum()
{
if (this.root == null)
{
return;
}
// Use to collect vertical sum result
var record = new Map();
this.findVerticalSum(this.root, 0, record);
// Use to collect range of print data from left to right
var min = Number.MAX_VALUE;
var max = -Number.MAX_VALUE;
// Find left and right boundary to display result
for (let [key, value] of record)
{
if (min > key)
{
min = key;
}
if (max < key)
{
max = key;
}
}
// Display the resultant value from left to right order
while (min <= max)
{
process.stdout.write(" " + record.get(min));
min++;
}
}
}
function main()
{
var tree = new BinaryTree();
/*
Binary Tree
-----------------------
4
/ \
3 10
/ / \
2 9 11
/ \
5 12
/ \
8 7
*/
// Add node in binary tree
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(3);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(10);
tree.root.right.right = new TreeNode(11);
tree.root.right.left = new TreeNode(9);
tree.root.right.left.left = new TreeNode(5);
tree.root.right.left.right = new TreeNode(12);
tree.root.right.left.right.right = new TreeNode(7);
tree.root.right.left.right.left = new TreeNode(8);
tree.verticalSum();
}
main();
Output
2 8 21 22 18
import sys
# Python 3 Program
# Vertical sum of given binary tree efficiently
# Binary Tree node
class TreeNode :
def __init__(self, data) :
# Set node value
self.data = data
self.left = None
self.right = None
class BinaryTree :
def __init__(self) :
self.root = None
def findVerticalSum(self, node, distance, record) :
if (node != None) :
if ((distance in record.keys())) :
# Update new vertical value
record[distance] = record.get(distance) + node.data
else :
# Add new vertical distance and value
record[distance] = node.data
# Visit left and right subtree recursively and find vertical sum
self.findVerticalSum(node.left, distance - 1, record)
self.findVerticalSum(node.right, distance + 1, record)
def verticalSum(self) :
if (self.root == None) :
return
# Use to collect vertical sum result
record = dict()
self.findVerticalSum(self.root, 0, record)
# Use to collect range of print data from left to right
min = sys.maxsize
max = -sys.maxsize
for key, value in record.items() :
if (min > key) :
min = key
if (max < key) :
max = key
# Display the resultant value from left to right order
while (min <= max) :
print(" ", record.get(min), end = "")
min += 1
def main() :
tree = BinaryTree()
# Binary Tree
# -----------------------
# 4
# / \
# 3 10
# / / \
# 2 9 11
# / \
# 5 12
# / \
# 8 7
# Add node in binary tree
tree.root = TreeNode(4)
tree.root.left = TreeNode(3)
tree.root.left.left = TreeNode(2)
tree.root.right = TreeNode(10)
tree.root.right.right = TreeNode(11)
tree.root.right.left = TreeNode(9)
tree.root.right.left.left = TreeNode(5)
tree.root.right.left.right = TreeNode(12)
tree.root.right.left.right.right = TreeNode(7)
tree.root.right.left.right.left = TreeNode(8)
tree.verticalSum()
if __name__ == "__main__": main()
Output
2 8 21 22 18
# Ruby Program
# Vertical sum of given binary tree efficiently
# Binary Tree node
class TreeNode
# Define the accessor and reader of class TreeNode
attr_reader :data, :left, :right
attr_accessor :data, :left, :right
def initialize(data)
# Set node value
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 findVerticalSum(node, distance, record)
if (node != nil)
if (record.key?(distance))
# Update new vertical value
record[distance] = record[distance] + node.data
else
# Add new vertical distance and value
record[distance] = node.data
end
# Visit left and right subtree recursively and find vertical sum
self.findVerticalSum(node.left, distance - 1, record)
self.findVerticalSum(node.right, distance + 1, record)
end
end
def verticalSum()
if (self.root == nil)
return
end
# Use to collect vertical sum result
record = Hash.new()
self.findVerticalSum(self.root, 0, record)
# Use to collect range of print data from left to right
min = (2 ** (0. size * 8 - 2))
max = -(2 ** (0. size * 8 - 2))
# Find left and right boundary to display result
record.each { | key, value |
if (min > key)
min = key
end
if (max < key)
max = key
end
}
# Display the resultant value from left to right order
while (min <= max)
print(" ", record[min])
min += 1
end
end
end
def main()
tree = BinaryTree.new()
# Binary Tree
# -----------------------
# 4
# / \
# 3 10
# / / \
# 2 9 11
# / \
# 5 12
# / \
# 8 7
# Add node in binary tree
tree.root = TreeNode.new(4)
tree.root.left = TreeNode.new(3)
tree.root.left.left = TreeNode.new(2)
tree.root.right = TreeNode.new(10)
tree.root.right.right = TreeNode.new(11)
tree.root.right.left = TreeNode.new(9)
tree.root.right.left.left = TreeNode.new(5)
tree.root.right.left.right = TreeNode.new(12)
tree.root.right.left.right.right = TreeNode.new(7)
tree.root.right.left.right.left = TreeNode.new(8)
tree.verticalSum()
end
main()
Output
2 8 21 22 18
import scala.collection.mutable._;
// Scala Program
// Vertical sum of given binary tree efficiently
// Binary Tree node
class TreeNode(var data: Int,
var left: TreeNode,
var right: TreeNode)
{
def this(data: Int)
{
// Set node value
this(data,null,null);
}
}
class BinaryTree(var root: TreeNode)
{
def this()
{
this(null);
}
def findVerticalSum(node: TreeNode,
distance: Int,
record: HashMap[Int, Int]): Unit = {
if (node != null)
{
if (record.contains(distance))
{
// Update new vertical value
record.addOne(distance, record.get(distance).get + node.data);
}
else
{
// Add new vertical distance and value
record.addOne(distance, node.data);
}
// Visit left and right subtree recursively and find vertical sum
findVerticalSum(node.left, distance - 1, record);
findVerticalSum(node.right, distance + 1, record);
}
}
def verticalSum(): Unit = {
if (this.root == null)
{
return;
}
// Use to collect vertical sum result
var record: HashMap[Int, Int] = new HashMap[Int, Int]();
this.findVerticalSum(this.root, 0, record);
// Use to collect range of print data from left to right
var min: Int = Int.MaxValue;
var max: Int = Int.MinValue;
// Find left and right boundary to display result
for ((key, value) <- record)
{
if (min > key)
{
min = key;
}
if (max < key)
{
max = key;
}
}
// Display the resultant value from left to right order
while (min <= max)
{
print(" " + record.get(min).get);
min += 1;
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var tree: BinaryTree = new BinaryTree();
/*
Binary Tree
-----------------------
4
/ \
3 10
/ / \
2 9 11
/ \
5 12
/ \
8 7
*/
// Add node in binary tree
tree.root = new TreeNode(4);
tree.root.left = new TreeNode(3);
tree.root.left.left = new TreeNode(2);
tree.root.right = new TreeNode(10);
tree.root.right.right = new TreeNode(11);
tree.root.right.left = new TreeNode(9);
tree.root.right.left.left = new TreeNode(5);
tree.root.right.left.right = new TreeNode(12);
tree.root.right.left.right.right = new TreeNode(7);
tree.root.right.left.right.left = new TreeNode(8);
tree.verticalSum();
}
}
Output
2 8 21 22 18
import Foundation;
// Swift 4 Program
// Vertical sum of given binary tree efficiently
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode? ;
var right: TreeNode? ;
init(_ data: Int)
{
// Set node value
self.data = data;
self.left = nil;
self.right = nil;
}
}
class BinaryTree
{
var root: TreeNode? ;
init()
{
self.root = nil;
}
func findVerticalSum(_ node: TreeNode? ,
_ distance : Int,
_ record: inout[Int : Int])
{
if (node != nil)
{
if (record.keys.contains(distance))
{
// Update new vertical value
record[distance] = record[distance]! + node!.data;
}
else
{
// Add new vertical distance and value
record[distance] = node!.data;
}
// Visit left and right subtree recursively and find vertical sum
self.findVerticalSum(node!.left, distance - 1, &record);
self.findVerticalSum(node!.right, distance + 1, &record);
}
}
func verticalSum()
{
if (self.root == nil)
{
return;
}
// Use to collect vertical sum result
var record = [Int : Int]();
self.findVerticalSum(self.root, 0, &record);
// Use to collect range of print data from left to right
var min: Int = Int.max;
var max: Int = Int.min;
// Find left and right boundary to display result
for (key, _) in record
{
if (min > key)
{
min = key;
}
if (max < key)
{
max = key;
}
}
// Display the resultant value from left to right order
while (min <= max)
{
print(" ", record[min]!, terminator: "");
min += 1;
}
}
}
func main()
{
let tree: BinaryTree = BinaryTree();
/*
Binary Tree
-----------------------
4
/ \
3 10
/ / \
2 9 11
/ \
5 12
/ \
8 7
*/
// Add node in binary tree
tree.root = TreeNode(4);
tree.root!.left = TreeNode(3);
tree.root!.left!.left = TreeNode(2);
tree.root!.right = TreeNode(10);
tree.root!.right!.right = TreeNode(11);
tree.root!.right!.left = TreeNode(9);
tree.root!.right!.left!.left = TreeNode(5);
tree.root!.right!.left!.right = TreeNode(12);
tree.root!.right!.left!.right!.right = TreeNode(7);
tree.root!.right!.left!.right!.left = TreeNode(8);
tree.verticalSum();
}
main();
Output
2 8 21 22 18
// Kotlin Program
// Vertical sum of given binary tree efficiently
// Binary Tree node
class TreeNode
{
var data: Int;
var left: TreeNode ? ;
var right: TreeNode ? ;
constructor(data: Int)
{
// Set node value
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree
{
var root: TreeNode ? ;
constructor()
{
this.root = null;
}
fun findVerticalSum(node: TreeNode ? ,
distance : Int,
record: MutableMap < Int, Int > ): Unit
{
if (node != null)
{
if (record.containsKey(distance))
{
// Update new vertical value
record.put(distance, record.getValue(distance) + node.data);
}
else
{
// Add new vertical distance and value
record.put(distance, node.data);
}
// Visit left and right subtree recursively and find vertical sum
this.findVerticalSum(node.left, distance - 1, record);
this.findVerticalSum(node.right, distance + 1, record);
}
}
fun verticalSum(): Unit
{
if (this.root == null)
{
return;
}
// Use to collect vertical sum result
var record = mutableMapOf<Int, Int>();
this.findVerticalSum(this.root, 0, record);
// Use to collect range of print data from left to right
var min: Int = Int.MAX_VALUE;
var max: Int = Int.MIN_VALUE;
// Find left and right boundary to display result
for ((key, _) in record)
{
if (min > key)
{
min = key;
}
if (max < key)
{
max = key;
}
}
// Display the resultant value from left to right order
while (min <= max)
{
print(" " + record.getValue(min));
min += 1;
}
}
}
fun main(args: Array < String > ): Unit
{
val tree: BinaryTree = BinaryTree();
/*
Binary Tree
-----------------------
4
/ \
3 10
/ / \
2 9 11
/ \
5 12
/ \
8 7
*/
// Add node in binary tree
tree.root = TreeNode(4);
tree.root?.left = TreeNode(3);
tree.root?.left?.left = TreeNode(2);
tree.root?.right = TreeNode(10);
tree.root?.right?.right = TreeNode(11);
tree.root?.right?.left = TreeNode(9);
tree.root?.right?.left?.left = TreeNode(5);
tree.root?.right?.left?.right = TreeNode(12);
tree.root?.right?.left?.right?.right = TreeNode(7);
tree.root?.right?.left?.right?.left = TreeNode(8);
tree.verticalSum();
}
Output
2 8 21 22 18
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