title

L21. Vertical Order Traversal of Binary Tree | C++ | Java

description

Entire DSA Course: https://takeuforward.org/strivers-a2z-dsa-course/strivers-a2z-dsa-course-sheet-2/
Check our Website: https://www.takeuforward.org/
Linkedin/Instagram/Telegram: https://linktr.ee/takeUforward
#treeSeries #striver #placements

detail

{'title': 'L21. Vertical Order Traversal of Binary Tree | C++ | Java', 'heatmap': [{'end': 403.764, 'start': 376.67, 'weight': 0.765}, {'end': 816.936, 'start': 803.05, 'weight': 0.802}, {'end': 922.262, 'start': 860.84, 'weight': 0.727}], 'summary': 'Relevel by unacademy provides skill-based tests offering 1000+ job openings from 50+ indian companies and unicorn startups, eliminating traditional experience requirements. the chapter discusses the vertical order traversal of a binary tree, emphasizing efficient traversal and sorting of nodes in ascending order of verticals and levels using data structures like queues, maps, and multi sets, resulting in a time complexity of o(n log n) and space complexity of o(n).', 'chapters': [{'end': 34.658, 'segs': [{'end': 42.923, 'src': 'embed', 'start': 17.808, 'weight': 0, 'content': [{'end': 24.492, 'text': 'If you use a platform like Relevel by Unacademy, it conducts a test which is completely based on skills and you need to perform in your chosen field.', 'start': 17.808, 'duration': 6.684}, {'end': 30.976, 'text': 'Relevel has around 1000 plus job openings by 50 plus top Indian companies and unicorn startups.', 'start': 24.712, 'duration': 6.264}, {'end': 34.658, 'text': 'What you need to do is you just need to register for this test, apply on the test,', 'start': 31.236, 'duration': 3.422}, {'end': 37.48, 'text': 'and after that your interview will be scheduled and you will be hired.', 'start': 34.658, 'duration': 2.822}, {'end': 42.923, 'text': 'And the best thing about this is the Relevel tests are free and you can check out all the links in the description below.', 'start': 37.72, 'duration': 5.203}], 'summary': 'Relevel by unacademy offers skill-based test with 1000+ job openings from 50+ top indian companies and unicorn startups, all free of cost.', 'duration': 25.115, 'max_score': 17.808, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/q_a6lpbKJdw/pics/q_a6lpbKJdw17808.jpg'}], 'start': 1.578, 'title': "Relevel by unacademy's experience-based job opportunities", 'summary': "Highlights relevel by unacademy's skill-based tests offering 1000+ job openings from 50+ indian companies and unicorn startups, eliminating traditional experience requirements.", 'chapters': [{'end': 34.658, 'start': 1.578, 'title': 'Relevel by unacademy: experience-based job opportunities', 'summary': 'Highlights how relevel by unacademy offers experience-based job opportunities by conducting skill-based tests, with 1000+ job openings from 50+ indian companies and unicorn startups, eliminating the need for traditional experience requirements.', 'duration': 33.08, 'highlights': ['Relevel by Unacademy provides a platform for skill-based tests, eliminating traditional experience requirements.', 'Relevel has 1000+ job openings by 50+ top Indian companies and unicorn startups.', 'The platform conducts tests completely based on skills and performance in the chosen field.']}], 'duration': 33.08, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/q_a6lpbKJdw/pics/q_a6lpbKJdw1578.jpg', 'highlights': ['Relevel by Unacademy provides a platform for skill-based tests, eliminating traditional experience requirements.', 'Relevel has 1000+ job openings by 50+ top Indian companies and unicorn startups.', 'The platform conducts tests completely based on skills and performance in the chosen field.']}, {'end': 490.409, 'segs': [{'end': 82.322, 'src': 'embed', 'start': 56.959, 'weight': 4, 'content': [{'end': 62.203, 'text': 'so you must be understanding what is the problem by the name vertical order right.', 'start': 56.959, 'duration': 5.244}, {'end': 70.569, 'text': 'so if I try to draw vertical lines in this particular binary tree, this will be the first vertical line that will be drawn.', 'start': 62.203, 'duration': 8.366}, {'end': 78.878, 'text': 'so I can say in the first vertical order we have four right right after that we will be having a line which will have two and five.', 'start': 70.569, 'duration': 8.309}, {'end': 82.322, 'text': 'so the next vertical line should have two and five.', 'start': 78.878, 'duration': 3.444}], 'summary': 'Binary tree has 4 nodes in first vertical order, 2 in the next.', 'duration': 25.363, 'max_score': 56.959, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/q_a6lpbKJdw/pics/q_a6lpbKJdw56959.jpg'}, {'end': 134.097, 'src': 'embed', 'start': 107.644, 'weight': 5, 'content': [{'end': 113.908, 'text': 'At the next vertical we have, 3 and at the next vertical we have again 10.', 'start': 107.644, 'duration': 6.264}, {'end': 116.269, 'text': 'now there is something to observe.', 'start': 113.908, 'duration': 2.361}, {'end': 122.332, 'text': 'the first thing was if nodes are overlapping, just make sure you take the smaller one.', 'start': 116.269, 'duration': 6.063}, {'end': 129.495, 'text': "if there are same nodes, doesn't matter like there can be similar value nodes in the binary tree.", 'start': 122.332, 'duration': 7.163}, {'end': 134.097, 'text': 'what matters is you have to write the vertical order from left to write.', 'start': 129.495, 'duration': 4.602}], 'summary': 'Node values: 3, 10. overlapping nodes: take smaller one. write vertical order left to right.', 'duration': 26.453, 'max_score': 107.644, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/q_a6lpbKJdw/pics/q_a6lpbKJdw107644.jpg'}, {'end': 181.994, 'src': 'embed', 'start': 158.45, 'weight': 0, 'content': [{'end': 166.064, 'text': 'you have to return a vector of vector or a list of list which describes the vertical order traversal of a binary tree.', 'start': 158.45, 'duration': 7.614}, {'end': 171.528, 'text': 'so, in order to solve this problem, Can we actually consider this as one of the verticals?', 'start': 166.064, 'duration': 5.464}, {'end': 173.569, 'text': 'This as another vertical.', 'start': 172.349, 'duration': 1.22}, {'end': 175.29, 'text': 'This as another vertical.', 'start': 174.13, 'duration': 1.16}, {'end': 176.631, 'text': 'This as another vertical.', 'start': 175.57, 'duration': 1.061}, {'end': 178.012, 'text': 'This as another vertical.', 'start': 177.051, 'duration': 0.961}, {'end': 181.994, 'text': 'We will be like, yes, Trevor, we definitely can consider that.', 'start': 178.032, 'duration': 3.962}], 'summary': 'Return vertical order traversal of a binary tree. consider multiple verticals.', 'duration': 23.544, 'max_score': 158.45, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/q_a6lpbKJdw/pics/q_a6lpbKJdw158450.jpg'}, {'end': 403.764, 'src': 'heatmap', 'start': 339.647, 'weight': 1, 'content': [{'end': 340.508, 'text': 'I think the job will be done.', 'start': 339.647, 'duration': 0.861}, {'end': 343.71, 'text': 'So in short, the question is very simple.', 'start': 341.428, 'duration': 2.282}, {'end': 350.996, 'text': 'I need to traverse for every node and I need to assign the verticals and the levels to every node.', 'start': 344.351, 'duration': 6.645}, {'end': 355.358, 'text': 'perfect. so you can do that using any traversal.', 'start': 351.636, 'duration': 3.722}, {'end': 359.18, 'text': "so what i'll do is i'll do this using the level order traversal.", 'start': 355.358, 'duration': 3.822}, {'end': 362.722, 'text': 'you can try this using in order, pre-order poster or whatever you feel like.', 'start': 359.18, 'duration': 3.542}, {'end': 364.103, 'text': 'you can try that.', 'start': 362.722, 'duration': 1.381}, {'end': 367.805, 'text': "so what i'll do is i will initially take a queue data structure.", 'start': 364.103, 'duration': 3.702}, {'end': 376.67, 'text': "okay, and in this queue data structure i'll be basically storing the node, the vertical and the level.", 'start': 367.805, 'duration': 8.865}, {'end': 385.811, 'text': "okay, that is what i will be doing and Along with that I'll be carrying a data structure of map which is having integer.", 'start': 376.67, 'duration': 9.141}, {'end': 388.793, 'text': 'Again, for Java people, you can carry something like tree map.', 'start': 386.231, 'duration': 2.562}, {'end': 395.938, 'text': 'And on this vertical, like assuming this guy to be vertical, so on every vertical, there will be multiple levels.', 'start': 389.534, 'duration': 6.404}, {'end': 403.764, 'text': "So for a level, I'll again carry, because for every level, like as you see over here, for level two, there were multiple nodes.", 'start': 396.459, 'duration': 7.305}], 'summary': 'Traversing every node to assign verticals and levels using level order traversal and a queue data structure.', 'duration': 49.146, 'max_score': 339.647, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/q_a6lpbKJdw/pics/q_a6lpbKJdw339647.jpg'}, {'end': 479.221, 'src': 'embed', 'start': 436.09, 'weight': 3, 'content': [{'end': 437.151, 'text': 'Like this can also be nine.', 'start': 436.09, 'duration': 1.061}, {'end': 439.393, 'text': 'okay, so there can be repeated of values.', 'start': 437.651, 'duration': 1.742}, {'end': 442.176, 'text': 'so please make sure you store like this.', 'start': 439.393, 'duration': 2.783}, {'end': 449.425, 'text': 'so, map of integer this represents the verticals, now each verticals.', 'start': 442.176, 'duration': 7.249}, {'end': 455.603, 'text': 'i will be representing a level, multiple levels on every vertical, on every level.', 'start': 449.425, 'duration': 6.178}, {'end': 457.885, 'text': 'there might be multi nodes, okay.', 'start': 455.603, 'duration': 2.282}, {'end': 464.412, 'text': "so this is what, uh, data structure you'll be using to store all the verticals and levels.", 'start': 457.885, 'duration': 6.527}, {'end': 479.221, 'text': 'mugged, okay, and in java what you can use is something like a tree map of int comma, again a tree map of int teacher, instead of a multi set.', 'start': 464.412, 'duration': 14.809}], 'summary': 'Use treemap in java to store verticals and levels of a data structure.', 'duration': 43.131, 'max_score': 436.09, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/q_a6lpbKJdw/pics/q_a6lpbKJdw436090.jpg'}], 'start': 34.658, 'title': 'Binary tree traversal', 'summary': 'Discusses the vertical order traversal of a binary tree, emphasizing drawing vertical lines, handling overlapping nodes, and returning a vector of vertical order traversal. it also covers assigning verticals and levels to nodes, using data structures like queues, maps, and multi sets, to ensure efficient traversal and sorting of nodes in ascending order of verticals and levels.', 'chapters': [{'end': 181.994, 'start': 34.658, 'title': 'Vertical order traversal', 'summary': 'Discusses the vertical order traversal of a binary tree, highlighting the process of drawing vertical lines, handling overlapping nodes, and returning a vector of vertical order traversal.', 'duration': 147.336, 'highlights': ['The chapter explains the process of drawing vertical lines in a binary tree to identify the vertical order traversal, with examples of the first and subsequent vertical lines.', 'It emphasizes the handling of overlapping nodes by writing the smaller value first and then the greater value, and underscores the importance of listing nodes from left to right in case of similar value nodes.', 'The chapter outlines the objective of returning a vector of vector or a list of list, describing the vertical order traversal of a binary tree, thereby providing a clear understanding of the expected output format.']}, {'end': 490.409, 'start': 182.655, 'title': 'Assigning verticals and levels to nodes', 'summary': 'Discusses the process of assigning verticals and levels to nodes to simplify the problem, using data structures like queues, maps, and multi sets, to ensure efficient traversal and sorting of nodes in ascending order of verticals and levels.', 'duration': 307.754, 'highlights': ['The chapter discusses the process of assigning verticals and levels to nodes to simplify the problem The speaker talks about simplifying the problem by assigning verticals and levels to nodes, which helps in organizing the data structure efficiently.', 'using data structures like queues, maps, and multi sets The speaker emphasizes the use of data structures such as queues, maps, and multi sets to organize and manage the nodes based on their verticals and levels.', 'ensure efficient traversal and sorting of nodes in ascending order of verticals and levels The approach aims to ensure efficient traversal and sorting of nodes by iterating in ascending order of verticals and levels, using appropriate data structures for maintaining sorted order.']}], 'duration': 455.751, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/q_a6lpbKJdw/pics/q_a6lpbKJdw34658.jpg', 'highlights': ['The chapter outlines the objective of returning a vector of vector or a list of list, describing the vertical order traversal of a binary tree, thereby providing a clear understanding of the expected output format.', 'The approach aims to ensure efficient traversal and sorting of nodes by iterating in ascending order of verticals and levels, using appropriate data structures for maintaining sorted order.', 'The speaker emphasizes the use of data structures such as queues, maps, and multi sets to organize and manage the nodes based on their verticals and levels.', 'The chapter discusses the process of assigning verticals and levels to nodes to simplify the problem, helping in organizing the data structure efficiently.', 'The chapter explains the process of drawing vertical lines in a binary tree to identify the vertical order traversal, with examples of the first and subsequent vertical lines.', 'It emphasizes the handling of overlapping nodes by writing the smaller value first and then the greater value, and underscores the importance of listing nodes from left to right in case of similar value nodes.']}, {'end': 1124.536, 'segs': [{'end': 759.875, 'src': 'embed', 'start': 735.265, 'weight': 0, 'content': [{'end': 740.827, 'text': 'so that that is how you can definitely get something as a vertical order traversal.', 'start': 735.265, 'duration': 5.562}, {'end': 742.108, 'text': 'so again i have.', 'start': 740.827, 'duration': 1.281}, {'end': 746.509, 'text': "i've done using the level order traversal, which uses a queue data structure.", 'start': 742.108, 'duration': 4.401}, {'end': 748.47, 'text': 'you can do this using in order.', 'start': 746.509, 'duration': 1.961}, {'end': 751.952, 'text': 'the sole idea is very simple whenever you move left,', 'start': 748.47, 'duration': 3.482}, {'end': 757.254, 'text': 'just vertical order and level and whenever you move right the vertical order and level you can use any traversal.', 'start': 751.952, 'duration': 5.302}, {'end': 759.875, 'text': "to move left and to move right doesn't matter.", 'start': 757.254, 'duration': 2.621}], 'summary': 'Vertical order traversal using queue data structure for any traversal.', 'duration': 24.61, 'max_score': 735.265, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/q_a6lpbKJdw/pics/q_a6lpbKJdw735265.jpg'}, {'end': 835.443, 'src': 'heatmap', 'start': 803.05, 'weight': 0.802, 'content': [{'end': 810.213, 'text': "just keep on doing the level order traversal and what you will do is you'll take the node right, you'll take the vertical order,", 'start': 803.05, 'duration': 7.163}, {'end': 816.936, 'text': "you'll take the level and after that what you'll do is at first just make sure you insert that into your data structure.", 'start': 810.213, 'duration': 6.723}, {'end': 825.76, 'text': "so first in vertical x of that, in the level y, just insert this guy, because it's a multi-set.", 'start': 816.936, 'duration': 8.824}, {'end': 835.443, 'text': 'So you insert that, right? After that, if there is a left, you take that left and insert it into the queue by vertical minus one and level plus one.', 'start': 825.8, 'duration': 9.643}], 'summary': 'Perform level order traversal and insert nodes into a data structure by vertical and level, handling left and right nodes accordingly.', 'duration': 32.393, 'max_score': 803.05, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/q_a6lpbKJdw/pics/q_a6lpbKJdw803050.jpg'}, {'end': 922.262, 'src': 'heatmap', 'start': 860.84, 'weight': 0.727, 'content': [{'end': 864.183, 'text': "so if i'm saying p dot second, what does that signify?", 'start': 860.84, 'duration': 3.343}, {'end': 868.628, 'text': 'that basically signifies a map of int like levels.', 'start': 864.183, 'duration': 4.445}, {'end': 872.677, 'text': "it's level and multi-set on that right?", 'start': 869.716, 'duration': 2.961}, {'end': 876.879, 'text': 'So p.second will traverse that and you have taken an answer right?', 'start': 873.197, 'duration': 3.682}, {'end': 882.461, 'text': "So what you're doing is you're taking a column and in that column, like in that level, right?", 'start': 877.179, 'duration': 5.282}, {'end': 888.943, 'text': "In that, how many, whatever levels are there, just make sure at every level you're inserting right at the end,", 'start': 882.561, 'duration': 6.382}, {'end': 891.164, 'text': 'like column.pushback or column.insert.', 'start': 888.943, 'duration': 2.221}, {'end': 894.445, 'text': "whatever you want to do, you're inserting the entire multi-set.", 'start': 891.164, 'duration': 3.281}, {'end': 901.669, 'text': "Like, let's assume, for a vertical traversal zero, we had level zero, we had level one.", 'start': 894.906, 'duration': 6.763}, {'end': 906.812, 'text': 'so first we traveled for zero, got the multi set inserted into the column.', 'start': 901.669, 'duration': 5.143}, {'end': 910.074, 'text': 'next level, once multi set we got inserted here.', 'start': 906.812, 'duration': 3.262}, {'end': 912.676, 'text': 'next level, two multi set we got, we inserted here.', 'start': 910.074, 'duration': 2.602}, {'end': 913.857, 'text': 'that is what we have done.', 'start': 912.676, 'duration': 1.181}, {'end': 922.262, 'text': 'once we have got this entire level, like entire vertical order, entire vertical, we will insert that vertical into the answer.', 'start': 913.857, 'duration': 8.405}], 'summary': 'Using p.second to traverse map of int levels and inserting multi-sets into columns based on vertical traversal.', 'duration': 61.422, 'max_score': 860.84, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/q_a6lpbKJdw/pics/q_a6lpbKJdw860840.jpg'}, {'end': 1102.539, 'src': 'embed', 'start': 1070.116, 'weight': 1, 'content': [{'end': 1075.121, 'text': "so that's a big of n, because for every vertical you're creating a level and you're storing all the nodes.", 'start': 1070.116, 'duration': 5.005}, {'end': 1076.643, 'text': "so ultimately you're storing all the nodes.", 'start': 1075.121, 'duration': 1.522}, {'end': 1082.245, 'text': "So I can summarize the space complexity to be b gov n plus b gov n for the queue data structure that you're using.", 'start': 1076.903, 'duration': 5.342}, {'end': 1086.947, 'text': "Again, thrice of n is somewhere that is what you're using, root and two other variables.", 'start': 1082.565, 'duration': 4.382}, {'end': 1090.409, 'text': 'But yeah, I can just write it as b gov n is the space complexity.', 'start': 1087.187, 'duration': 3.222}, {'end': 1099.956, 'text': "Like, if I summarize it and I can say n log n to be the time complexity that I'm taking in order to do the vertical order traversal because of the multi-set or the priority queue that you're using.", 'start': 1090.429, 'duration': 9.527}, {'end': 1102.539, 'text': "So I hope you've understood the entire explanation as well as the code.", 'start': 1100.117, 'duration': 2.422}], 'summary': 'Space complexity is o(b^n) and time complexity is o(n log n) for vertical order traversal using priority queue.', 'duration': 32.423, 'max_score': 1070.116, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/q_a6lpbKJdw/pics/q_a6lpbKJdw1070116.jpg'}], 'start': 490.409, 'title': 'Vertical order traversal', 'summary': 'Explains the process of performing a vertical order traversal using a queue data structure in c++ and java, demonstrating the insertion of nodes and the manipulation of vertical and level values. it also involves creating a map of levels and multi-sets, using tree maps and priority queues, resulting in a time complexity of o(n log n) and space complexity of o(n).', 'chapters': [{'end': 840.645, 'start': 490.409, 'title': 'Vertical order traversal', 'summary': 'Explains the process of performing a vertical order traversal using a queue data structure in c++ and java, demonstrating the insertion of nodes and the manipulation of vertical and level values.', 'duration': 350.236, 'highlights': ['The process of inserting nodes and manipulating vertical and level values is explained for performing a vertical order traversal using a queue data structure in C++ and Java. The explanation covers the insertion of nodes, manipulation of vertical and level values, and the use of a queue data structure in C++ and Java.', 'The method of level order traversal using a queue data structure and the insertion of nodes into a data structure is demonstrated. The chapter demonstrates the process of level order traversal using a queue data structure and the insertion of nodes into a data structure.', 'The use of pairs in C++ and the use of couple in Java for storing node, vertical, and level is explained. The explanation covers the use of pairs in C++ and couple in Java for storing node, vertical, and level.']}, {'end': 1124.536, 'start': 841.165, 'title': 'Vertical order traversal', 'summary': 'Explains the process of performing a vertical order traversal in java, which involves creating a map of levels and multi-sets, using tree maps and priority queues, resulting in a time complexity of o(n log n) and space complexity of o(n).', 'duration': 283.371, 'highlights': ['The time complexity is O(n log n) due to the usage of multi-sets and priority queues for vertical order traversal in Java. The usage of multi-sets and priority queues contributes to the time complexity being O(n log n) for vertical order traversal in Java.', 'The space complexity is O(n) for the queue data structure and data storage for every vertical level. For every vertical level, the space complexity is O(n) due to the creation of levels and storage of all nodes, with an additional O(n) for the queue data structure.', 'The process involves creating a map of levels and multi-sets, using tree maps and priority queues for vertical order traversal. The explanation covers the creation of a map of levels and multi-sets, utilizing tree maps and priority queues for the vertical order traversal process.']}], 'duration': 634.127, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/q_a6lpbKJdw/pics/q_a6lpbKJdw490409.jpg', 'highlights': ['The process of inserting nodes and manipulating vertical and level values is explained for performing a vertical order traversal using a queue data structure in C++ and Java.', 'The time complexity is O(n log n) due to the usage of multi-sets and priority queues for vertical order traversal in Java.', 'The space complexity is O(n) for the queue data structure and data storage for every vertical level.']}], 'highlights': ['Relevel by Unacademy provides a platform for skill-based tests, eliminating traditional experience requirements.', 'Relevel has 1000+ job openings by 50+ top Indian companies and unicorn startups.', 'The platform conducts tests completely based on skills and performance in the chosen field.', 'The chapter outlines the objective of returning a vector of vector or a list of list, describing the vertical order traversal of a binary tree, thereby providing a clear understanding of the expected output format.', 'The approach aims to ensure efficient traversal and sorting of nodes by iterating in ascending order of verticals and levels, using appropriate data structures for maintaining sorted order.', 'The speaker emphasizes the use of data structures such as queues, maps, and multi sets to organize and manage the nodes based on their verticals and levels.', 'The chapter discusses the process of assigning verticals and levels to nodes to simplify the problem, helping in organizing the data structure efficiently.', 'The chapter explains the process of drawing vertical lines in a binary tree to identify the vertical order traversal, with examples of the first and subsequent vertical lines.', 'It emphasizes the handling of overlapping nodes by writing the smaller value first and then the greater value, and underscores the importance of listing nodes from left to right in case of similar value nodes.', 'The process of inserting nodes and manipulating vertical and level values is explained for performing a vertical order traversal using a queue data structure in C++ and Java.', 'The time complexity is O(n log n) due to the usage of multi-sets and priority queues for vertical order traversal in Java.', 'The space complexity is O(n) for the queue data structure and data storage for every vertical level.']}