Aug 14, 2016

Textual description of firstImageUrl

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

Location: Hyderabad, Telangana, India

13 comments:

  1. Wow, happy to see this awesome post. I hope this think help any newbie for their awesome work and by the way thanks for share this awesomeness, i thought this was a pretty interesting read when it comes to this topic. Thank you..
    Artificial Intelligence Course

    ReplyDelete
  2. I need to thank you for this very good read and i have bookmarked to check out new things from your post. Thank you very much for sharing such a useful article and will definitely saved and revisit your site.
    Data Science Course

    ReplyDelete
  3. Excellent Blog! I would like to thank you for the efforts you have made in writing this post. Gained lots of knowledge.
    Data Analytics Course

    ReplyDelete
  4. What an incredible message this is. Truly one of the best posts I have ever seen in my life. Wow, keep it up.
    AI Courses in Bangalore

    ReplyDelete
  5. Your site is truly cool and this is an extraordinary moving article and If it's not too much trouble share more like that. Thank You..
    Digital Marketing Course in Hyderabad

    ReplyDelete
  6. Awesome article. I enjoyed reading your articles. this can be really a good scan for me. wanting forward to reading new articles. maintain the nice work!
    Data Science Courses in Bangalore

    ReplyDelete
  7. Thank a lot. You have done excellent job. I enjoyed your blog . Nice efforts
    Data Science Certification in Hyderabad

    ReplyDelete
  8. I am sure it will help many people. Keep up the good work. It's very compelling and I enjoyed browsing the entire blog.
    Business Analytics Course in Bangalore

    ReplyDelete
  9. I bookmarked your website because this site contains valuable information. I am very satisfied with the quality and the presentation of the articles. Thank you so much for saving great things. I am very grateful for this site.

    Data Science Training in Bangalore

    ReplyDelete
  10. Wonderful blog found to be very impressive to come across such an awesome blog. I should really appreciate the blogger for the efforts they have put in to develop such amazing content for all the curious readers who are very keen on being updated across every corner. Ultimately, this is an awesome experience for the readers. Anyways, thanks a lot and keep sharing the content in the future too.

    Digital Marketing Training in Bangalore

    ReplyDelete
  11. 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
  12. The Extraordinary blog went amazed by the content that they have developed in a very descriptive manner. This type of content surely ensures the participants explore themselves. Hope you deliver the same near the future as well. Gratitude to the blogger for the efforts.

    Machine Learning Course in Bangalore

    ReplyDelete