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

7 Comments

  1. I found Habit to be a transparent site, a social hub that is a conglomerate of buyers and sellers willing to offer digital advice online at a decent cost.

    Artificial Intelligence Training in Bangalore

    ReplyDelete
  2. You have done excellent job Thanks a lot and I enjoyed your blog. Great Post.
    Data Science Certification in Hyderabad

    ReplyDelete
  3. A good blog always contains new and exciting information and as I read it I felt that this blog really has all of these qualities that make a blog.

    Digital Marketing Institute in Bangalore

    ReplyDelete
  4. Very nice job... Thanks for sharing this amazing and educative blog post!
    Data Science Training in Lucknow

    ReplyDelete
  5. I am impressed by the information that you have on this blog. It shows how well you understand this subject.
    Data Science Course in Ahmedabad

    ReplyDelete
  6. You know your projects stand out from the crowd. There is something special about them. I think they're all really cool!

    Business Analytics Course in Durgapur

    ReplyDelete
Previous Post Next Post