# 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(n2 )

```// 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) {
hmap.put(hd, list);
} else {
List<Integer> list2 = hmap.get(hd);
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.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) {
hmap.put(hd, list);
} else {
List<Integer> list2 = hmap.get(hd);
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