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 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
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
Đặt vé tại phòng vé Aivivu, tham khảo
ReplyDeletevé máy bay đi Mỹ bao nhiêu tiền
vé máy bay hà nội đi hồ chí minh
máy bay đà lạt hà nội
vietnam airlines nha trang
vé máy bay đi quy nhơn tháng 2
taxi sân bay giá rẻ
combo 4 đảo phú quốc
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..
ReplyDeleteArtificial Intelligence Course
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.
ReplyDeleteData Science Course
Excellent Blog! I would like to thank you for the efforts you have made in writing this post. Gained lots of knowledge.
ReplyDeleteData Analytics Course
What an incredible message this is. Truly one of the best posts I have ever seen in my life. Wow, keep it up.
ReplyDeleteAI Courses in Bangalore
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..
ReplyDeleteDigital Marketing Course in Hyderabad
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!
ReplyDeleteData Science Courses in Bangalore
Thank a lot. You have done excellent job. I enjoyed your blog . Nice efforts
ReplyDeleteData Science Certification in Hyderabad
I am sure it will help many people. Keep up the good work. It's very compelling and I enjoyed browsing the entire blog.
ReplyDeleteBusiness Analytics Course in Bangalore
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.
ReplyDeleteData Science Training in Bangalore
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.
ReplyDeleteDigital Marketing Training in Bangalore
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.
ReplyDeleteArtificial Intelligence Training in Bangalore
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.
ReplyDeleteMachine Learning Course in Bangalore
Great post happy to see this. I thought this was a pretty interesting read when it comes to this topic Information. Thanks..
ReplyDeleteArtificial Intelligence Course
Nice Post thank you very much for sharing such a useful information and will definitely saved and revisit your site and i have bookmarked to check out new things frm your post.
ReplyDeleteData Science Course
Thanks Your post is so cool and this is an extraordinary moving article and If it's not too much trouble share more like that.
ReplyDeleteDigital Marketing Course in Hyderabad
You have done excellent job Thanks a lot and I enjoyed your blog. Great Post.
ReplyDeleteData Science Certification in Hyderabad
Really impressed! Everything is a very open and very clear clarification of the issues. It contains true facts. Your website is very valuable. Thanks for sharing.
ReplyDeleteDigital Marketing Training in Bangalore
A good blog always contains new and exciting information, and reading it I feel like this blog really has all of these qualities that make it a blog.
ReplyDeleteArtificial Intelligence Training in Bangalore
Happy to chat on your blog, I feel like I can't wait to read more reliable posts and think we all want to thank many blog posts to share with us.
ReplyDeleteMachine Learning Course in Bangalore
I wanted to leave a little comment to support you and wish you the best of luck. We wish you the best of luck in all of your blogging endeavors.
ReplyDeleteData Science Training in Bangalore
It is a very helpful and very informative blog. I really learned a lot from it thanks for sharing.
ReplyDeleteData Analytics Course
I am sure it will help many people. Keep up the good work. It's very compelling and I enjoyed browsing the entire blog.
ReplyDeleteBusiness Analytics Course in Bangalore
Very informative blog! There is so much information here that can help thank you for sharing.
ReplyDeleteData Science Syllabus
This is an informative and knowledgeable article. therefore, I would like to thank you for your effort in writing this article.
ReplyDeleteBest Digital Marketing Courses in Bangalore
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.
ReplyDeleteDigital Marketing Institute in Bangalore
You have done a great job and will definitely dig it and personally recommend to my friends. Thank You.
ReplyDeleteData Science Online Training
Superb Information and really appreciated with it and this is fine to read and valuable. I like it.
ReplyDeleteDigital Marketing Course fees in Hyderabad
ReplyDeleteThe blog is informative and very useful therefore, I would like to thank you for your effort in writing this article.
Data Analytics Course in Lucknow
Really this article is truly one of the best in article history and am a collector of old "items" and sometimes read new items if i find them interesting which is one that I found quite fascinating and should be part of my collection. Very good work!
ReplyDeleteData Scientist Course in Gurgaon
I have read your article, it is very informative and useful to me, I admire the valuable information you offer in your articles. Thanks for posting it ...
ReplyDeleteBusiness Analytics Course in Patna
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.
ReplyDeleteData Science Institutes in Bangalore
Very informative message! There is so much information here that can help me thank you for sharing
ReplyDeleteData Analytics Course in Lucknow
So luck to come across your excellent blog, glad i found it. Keep posting new articles. Good luck.
ReplyDeleteData Science Course Details
Very nice job... Thanks for sharing this amazing and educative blog post!
ReplyDeleteData Science Training in Lucknow
I feel very grateful that I read this. It is very helpful and very informative and I really learned a lot from it, Keep posting new articles.
ReplyDeleteData Analytics Course in Ahmedabad
I finally found a great article here. Quality postings are essential to get visitors to visit the website, that's what this website offers.
ReplyDeleteData Science Training in Jabalpur
Really nice and interesting post. I was looking for this kind of information and enjoyed reading this one. Thanks for sharing.
ReplyDeleteData Scientist Course in Jabalpur
Very happy to find a good place for many here in the post, the writing is just great, thanks for the post.
ReplyDeleteData Science Course in Ernakulam
I am impressed by the information that you have on this blog. It shows how well you understand this subject.
ReplyDeleteData Science Course in Ahmedabad
You know your projects stand out from the crowd. There is something special about them. I think they're all really cool!
ReplyDeleteBusiness Analytics Course in Durgapur
I think this is a really good article. You make this information interesting and engaging. Thanks for sharing.
ReplyDeleteData Science Course in India
I am delighted to discover this page. I must thank you for the time you devoted to this particularly fantastic reading !! I really liked each part very much and also bookmarked you to see new information on your site.
ReplyDeleteBusiness Analytics Course in Durgapur
Really impressed! Information shared was very helpful Your website is very valuable. Thanks for sharing.
ReplyDeleteFood Processing Consultants