Display nodes of binary tree in a vertical line viewed from top and compute sum of vertical line nodes

Problem:- Display nodes of binary tree in a vertical line viewed from top.

Output:-  
Nodes at vertical line
56
11
23 78
12 43 12
18 98
99

Sum at vertical line 
Sum at 0 is/are 67
Sum at 1 is/are 116
Sum at 2 is/are 99
Sum at -3 is/are 56
Sum at -2 is/are 11
Sum at -1 is/are 101

Sample code - Order of O(n² )

// To find min and max horizontal distance.
public static void findMinMaxHorizontal(Node root, Values val, int hd) {
 if (root == null)
  return;
 if (hd < val.min) {
  val.min = hd;
 } else if (hd > val.max) {
  val.max = hd;
 }
 findMinMaxHorizontal(root.getLeftChild(), val, hd - 1);
 findMinMaxHorizontal(root.getRightChild(), val, hd + 1);
}

// order of o(N2) - worst case complexity
public static void printVerticalOrderOfON2(Node root) {
 Values val = new Values();
 findMinMaxHorizontal(root, val, 0);
 // System.out.println(val.min + " " + val.max);

 for (int i = val.min; i <= val.max; i++) {
  System.out.println("Nodes in horizontal distance  " + i
    + " is/are ");
  printVerticalLineNodes(root, i, 0);

  System.out.println();
 }

}

public static void printVerticalLineNodes(Node root, int line_no, int hd) {

 if (root == null)
  return;
 if (hd == line_no) {
  System.out.print(root.getData() + " ");
 }
 printVerticalLineNodes(root.getLeftChild(), line_no, hd - 1);
 printVerticalLineNodes(root.getRightChild(), line_no, hd + 1);
}
class Values {
 int min;
 int max;
}

Sample code using a HashMap  - Order of O(n ), space complexity also O(n) 

public static void printVerticalOrderHashMapbased(Node root,
  Map<Integer, List<Integer>> hmap, int hd) {
 if (root == null)
  return;
 if (hmap.get(hd) == null) {
  List<Integer> list = new LinkedList<Integer>();
  list.add(root.getData());
  hmap.put(hd, list);
 } else {
  List<Integer> list2 = hmap.get(hd);
  list2.add(root.getData());
  hmap.put(hd, list2);
 }

 printVerticalOrderHashMapbased(root.getLeftChild(), hmap, hd - 1);
 printVerticalOrderHashMapbased(root.getRightChild(), hmap, hd + 1);
}

Complete sample program

package com.devinline.trees;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class BinaryTreeVerticalSum {

// To find min and max horizontal distance.
public static void findMinMaxHorizontal(Node root, Values val, int hd) {
 if (root == null)
  return;
 if (hd < val.min) {
  val.min = hd;
 } else if (hd > val.max) {
  val.max = hd;
 }
 findMinMaxHorizontal(root.getLeftChild(), val, hd - 1);
 findMinMaxHorizontal(root.getRightChild(), val, hd + 1);
}

// order of o(N2) - worst case complexity
public static void printVerticalOrderOfON2(Node root) {
 Values val = new Values();
 findMinMaxHorizontal(root, val, 0);
 // System.out.println(val.min + " " + val.max);

 for (int i = val.min; i <= val.max; i++) {
  System.out.println("Nodes in horizontal distance  " + i
    + " is/are ");
  printVerticalLineNodes(root, i, 0);

  System.out.println();
 }

}

public static void printVerticalLineNodes(Node root, int line_no, int hd) {

 if (root == null)
  return;
 if (hd == line_no) {
  System.out.print(root.getData() + " ");
 }
 printVerticalLineNodes(root.getLeftChild(), line_no, hd - 1);
 printVerticalLineNodes(root.getRightChild(), line_no, hd + 1);
}

public static void printVerticalLineNodesSum(Node root, int hd,
  Map<Integer, Integer> hmap) {
 if (root == null)
  return;

 int prevSum = hmap.get(hd) == null ? 0 : hmap.get(hd);
 hmap.put(hd, prevSum + root.getData());

 printVerticalLineNodesSum(root.getLeftChild(), hd - 1, hmap);
 printVerticalLineNodesSum(root.getRightChild(), hd + 1, hmap);
}

public static void printVerticalOrderHashMapbased(Node root,
  Map<Integer, List<Integer>> hmap, int hd) {
 if (root == null)
  return;
 if (hmap.get(hd) == null) {
  List<Integer> list = new LinkedList<Integer>();
  list.add(root.getData());
  hmap.put(hd, list);
 } else {
  List<Integer> list2 = hmap.get(hd);
  list2.add(root.getData());
  hmap.put(hd, list2);
 }

 printVerticalOrderHashMapbased(root.getLeftChild(), hmap, hd - 1);
 printVerticalOrderHashMapbased(root.getRightChild(), hmap, hd + 1);
}

public static void main(String[] args) {
 BinaryTree bt = new BinaryTree();
 Node root = bt.createTree();
 System.out
 .println("\n====Print vertical elemets of order O(n2)===");
 printVerticalOrderOfON2(root);
 Map<Integer, List<Integer>> hmap2 = new HashMap<>();
 System.out
   .println("\n====Print vertical elemets using hashmap of order O(n)===");
 printVerticalOrderHashMapbased(root, hmap2, 0);
 System.out.println(hmap2.entrySet());
 for (int i : hmap2.keySet()) {
  System.out.println("Nodes with horizontal distance " + i
    + " is/are " + hmap2.get(i));
 }
 Map<Integer, Integer> hmap = new HashMap<>();
 printVerticalLineNodesSum(root, 0, hmap);
 System.out.println("\n===Print sum of vertical elements using hashmap====");
 for (int i : hmap.keySet()) {
  System.out.println("Sum of nodes at horizontal distance " + i
    + " is/are " + hmap.get(i));
 }
}
}

class Values {
int min;
int max;
}
class BinaryTree {
 Node root;

 public BinaryTree() {
  root = null;
 }
 public Node createTree() {
  if (root == null) {
   root = new Node(12);
  }
  root.setLeftChild(new Node(23));
  root.setRightChild(new Node(18));
  root.getLeftChild().setLeftChild(new Node(11));
  root.getLeftChild().setRightChild(new Node(43));
  root.getRightChild().setLeftChild(new Node(12));
  root.getLeftChild().getLeftChild().setLeftChild(new Node(56));
  root.getLeftChild().getLeftChild().setRightChild(new Node(78));
  root.getRightChild().getLeftChild().setRightChild(new Node(98));
  root.getRightChild().setRightChild(new Node(99));
  return root;
 } 
}

class Node {

 private int data;
 private Node leftChild;
 private Node rightChild;

 public Node(int data) {
  this.data = data;
  leftChild = null;
  rightChild = null;
 }

 public int getData() {
  return data;
 }

 public void setData(int data) {
  this.data = data;
 }

 public Node getLeftChild() {
  return leftChild;
 }

 public void setLeftChild(Node leftChild) {
  this.leftChild = leftChild;
 }

 public Node getRightChild() {
  return rightChild;
 }

 public void setRightChild(Node rightChild) {
  this.rightChild = rightChild;
 }

}

Sample output:-

====Print vertical elemets of order O(n2)===
Nodes in horizontal distance  -3 is/are
56
Nodes in horizontal distance  -2 is/are
11
Nodes in horizontal distance  -1 is/are
23 78
Nodes in horizontal distance  0 is/are
12 43 12
Nodes in horizontal distance  1 is/are
18 98
Nodes in horizontal distance  2 is/are
99

====Print vertical elemets using hashmap of order O(n)===
[0=[12, 43, 12], 1=[18, 98], 2=[99], -3=[56], -2=[11], -1=[23, 78]]
Nodes with horizontal distance 0 is/are [12, 43, 12]
Nodes with horizontal distance 1 is/are [18, 98]
Nodes with horizontal distance 2 is/are [99]
Nodes with horizontal distance -3 is/are [56]
Nodes with horizontal distance -2 is/are [11]
Nodes with horizontal distance -1 is/are [23, 78]

===Print sum of vertical elements using hashmap====
Sum of nodes at horizontal distance 0 is/are 67
Sum of nodes at horizontal distance 1 is/are 116
Sum of nodes at horizontal distance 2 is/are 99
Sum of nodes at horizontal distance -3 is/are 56
Sum of nodes at horizontal distance -2 is/are 11
Sum of nodes at horizontal distance -1 is/are 101