Print the Vertical Sum in binary Tree .

by

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

What is Vertical Order Sum

Vertical Order Sum Exampleas 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).
  • Vertical Order Sum Implementation
    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;
}
}

view raw
VerticalOrderSum.java
hosted with ❤ by GitHub

Output:

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

Related Posts: