Skip to main content

Vertical sum of given binary tree efficiently

Vertical order sum of binary tree nodes

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
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