Print the Vertical Sum in binary Tree .

Objective: – Given a binary tree, print it in vertical order sum

What is Vertical Order Sum

as you can see in the example above, [4],[2], [12],[3],[7] are the vertical order sum of the given binary tree.

Approach:

Do the inorder traversal.
Take a variable called level, when ever you fo left, do level++ AND when ever you go right do level–.
With step above we have separated out the levels vertically.
Now you need to add the elements of each level, so create a TreeMap and the (key,value) pair will be (level,Sum of elements).
Separate out the vertical levels

At the end iterate through the TreeMap and print the results.

Complete Code:

	import java.util.Set;
	import java.util.TreeMap;

	public class VerticalOrderSum {
	public static TreeMap<Integer, Integer> ht = new TreeMap<>();;
	public static int level;

	public void vertical(Node root, int level) {
	if (root == null) {
	return;
	}
	vertical(root.left, level+1);

	if (ht.get(level) != null) {
	int y = ht.get(level);
	ht.put(level, root.data + y);
	} else {
	ht.put(level, root.data);
	}
	vertical(root.right, level–1);
	}

	public void printResult(TreeMap ht) {
	// Iterator it = ht.keySet().iterator();
	Set<Integer> i = ht.keySet();
	for (int keys : i) {
	System.out.println("Level " + keys + " Sum : " + ht.get(keys));
	}
	}

	public static void main(String args[]) {
	Node root = new Node(1);
	root.left = new Node(2);
	root.right = new Node(3);
	root.left.left = new Node(4);
	root.left.right = new Node(5);
	root.right.left = new Node(6);
	root.right.right = new Node(7);

	VerticalOrderSum p = new VerticalOrderSum();
	p.vertical(root, 0);
	p.printResult(ht);
	}
	}

	class Node {
	int data;
	Node left;
	Node right;

	public Node(int data) {
	this.data = data;
	left = null;
	right = null;
	}
	}

Output:

Level -2 Sum : 7 
Level -1 Sum : 3 
Level 0 Sum : 12 
Level 1 Sum : 2 
Level 2 Sum : 4