title
L37. Morris Traversal | Preorder | Inorder | 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': 'L37. Morris Traversal | Preorder | Inorder | C++ | Java', 'heatmap': [{'end': 444.558, 'start': 425.545, 'weight': 0.795}, {'end': 1102.018, 'start': 1054.441, 'weight': 0.791}], 'summary': "Anacademy's releval platform promises job placement within a week with top companies, while the video introduces morris traversal for binary tree in-order and pre-order traversal, emphasizing its space efficiency achieving nearly o(n) time. additionally, it discusses threaded binary trees and time complexity for binary tree traversal.", 'chapters': [{'end': 37.974, 'segs': [{'end': 37.974, 'src': 'embed', 'start': 0.109, 'weight': 0, 'content': [{'end': 4.592, 'text': 'So before starting the video, I would love to thank Releval for sponsoring this entire 3 series.', 'start': 0.109, 'duration': 4.483}, {'end': 11.377, 'text': "So, if you're tired of waiting for companies to respond to your applications through different job portals, the next few seconds are very,", 'start': 5.093, 'duration': 6.284}, {'end': 18.203, 'text': "very important for you, because Releval by Anacademy is India's first hiring platform that can get you a job within a week itself.", 'start': 11.377, 'duration': 6.826}, {'end': 22.886, 'text': 'Yes, all you have to do is to register for the Releval test and within a week,', 'start': 18.303, 'duration': 4.583}, {'end': 27.97, 'text': "your interview will be scheduled with India's top companies and the top budding unicorns.", 'start': 22.886, 'duration': 5.084}, {'end': 34.373, 'text': 'So what are you waiting for? Make sure you check out the links in the description and apply for the reliable test because it is free.', 'start': 28.21, 'duration': 6.163}, {'end': 36.254, 'text': 'Hey everyone, welcome back to the channel.', 'start': 34.873, 'duration': 1.381}, {'end': 37.974, 'text': 'I hope you guys are doing extremely well.', 'start': 36.394, 'duration': 1.58}], 'summary': "Releval by anacademy is india's first hiring platform that can get you a job within a week; register for the releval test and get an interview with top companies and unicorns.", 'duration': 37.865, 'max_score': 0.109, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r4109.jpg'}], 'start': 0.109, 'title': 'Releval by anacademy', 'summary': "Introduces releval by anacademy, india's first hiring platform, claiming to secure a job within a week, with top companies and unicorns, by registering for their test, emphasizing its free nature and potential to speed up the application process.", 'chapters': [{'end': 37.974, 'start': 0.109, 'title': "Releval by anacademy: india's fast hiring platform", 'summary': "Introduces releval by anacademy, india's first hiring platform, which claims to secure a job within a week, with top companies and unicorns, by registering for their test, emphasizing its free nature and potential to speed up the application process.", 'duration': 37.865, 'highlights': ["Releval by Anacademy is India's first hiring platform that can get you a job within a week itself, with top companies and unicorns, by registering for their test.", "The Releval test can schedule your interview within a week with India's top companies and budding unicorns.", 'Releval test is highlighted as free to apply, providing a potential solution to the lengthy job application process.']}], 'duration': 37.865, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r4109.jpg', 'highlights': ["Releval by Anacademy is India's first hiring platform that can get you a job within a week itself, with top companies and unicorns, by registering for their test.", "The Releval test can schedule your interview within a week with India's top companies and budding unicorns.", 'Releval test is highlighted as free to apply, providing a potential solution to the lengthy job application process.']}, {'end': 529.657, 'segs': [{'end': 71.368, 'src': 'embed', 'start': 38.314, 'weight': 0, 'content': [{'end': 40.915, 'text': 'So today we will be discussing the Morris traversal.', 'start': 38.314, 'duration': 2.601}, {'end': 54.539, 'text': "So, in the first section of the video I'll be telling you how to find the inorder and right after that i'll just be doing a one line change to the in order and i will teach you how to find the pre-order using the morris traversal.", 'start': 41.256, 'duration': 13.283}, {'end': 58.04, 'text': 'i will be, uh, thinking what is special in morris traversal?', 'start': 54.539, 'duration': 3.501}, {'end': 60.221, 'text': 'we already know a recursive traversal.', 'start': 58.04, 'duration': 2.181}, {'end': 62.261, 'text': 'we already know a stack traversal.', 'start': 60.221, 'duration': 2.04}, {'end': 71.368, 'text': 'so if you know the recursive traversal, that actually takes up a big of end time And a big of n space, which is the auxiliary stack space right?', 'start': 62.261, 'duration': 9.107}], 'summary': 'Discusses morris traversal to find inorder and pre-order without additional space', 'duration': 33.054, 'max_score': 38.314, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r438314.jpg'}, {'end': 140.101, 'src': 'embed', 'start': 112.663, 'weight': 1, 'content': [{'end': 118.807, 'text': "now you have seen a lot of videos about morris traversal, but trust me, in this video i'm going to tell you the intuition.", 'start': 112.663, 'duration': 6.144}, {'end': 127.293, 'text': "yes, and i'll be coding it live, so that the code remains in your head forever, along with the intuition, and you can code it by yourself.", 'start': 118.807, 'duration': 8.486}, {'end': 128.693, 'text': "so let's get started.", 'start': 127.293, 'duration': 1.4}, {'end': 131.916, 'text': 'so what is the in order traversal of?', 'start': 128.693, 'duration': 3.223}, {'end': 134.017, 'text': 'so when i say in order, what does that mean?', 'start': 131.916, 'duration': 2.101}, {'end': 140.101, 'text': 'it basically means left, first, then the root and then something as the right.', 'start': 134.017, 'duration': 6.084}], 'summary': 'Live coding of in-order traversal with explanation.', 'duration': 27.438, 'max_score': 112.663, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r4112663.jpg'}, {'end': 189.915, 'src': 'embed', 'start': 161.654, 'weight': 2, 'content': [{'end': 166.418, 'text': "So, that's the inorder traversal for the binary tree on the left.", 'start': 161.654, 'duration': 4.764}, {'end': 175.084, 'text': 'Correct? Now, if you observe something, from 4, you are actually, like you traverse from 1 to 2, 2 to 4.', 'start': 167.018, 'duration': 8.066}, {'end': 179.587, 'text': 'And in the binary tree, you know the pointers are like this, like into the childs.', 'start': 175.084, 'duration': 4.503}, {'end': 189.915, 'text': "So from 4, if you had a backward, if you had a backward pointer which said after 4, why don't you go back to 2?", 'start': 180.128, 'duration': 9.787}], 'summary': 'In-order traversal of binary tree, 4-2-1, with a backward pointer from 4 to 2.', 'duration': 28.261, 'max_score': 161.654, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r4161654.jpg'}, {'end': 331.563, 'src': 'embed', 'start': 301.683, 'weight': 3, 'content': [{'end': 305.065, 'text': 'And in this right, this is a single subtree.', 'start': 301.683, 'duration': 3.382}, {'end': 307.106, 'text': 'So, over here, this is the last guy.', 'start': 305.445, 'duration': 1.661}, {'end': 313.37, 'text': 'So, after this, since the left subtree in order is completed, you go back to the root.', 'start': 307.547, 'duration': 5.823}, {'end': 315.212, 'text': 'So do you see a pattern?', 'start': 313.871, 'duration': 1.341}, {'end': 327.58, 'text': 'The pattern states from the last node of any subtree, you go back to the root like on the left, which is whichever is the last node of that subtree.', 'start': 315.672, 'duration': 11.908}, {'end': 331.563, 'text': 'you go back to the root right, and after that you again go back to the like.', 'start': 327.58, 'duration': 3.983}], 'summary': 'Pattern: from last subtree node, return to root', 'duration': 29.88, 'max_score': 301.683, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r4301683.jpg'}, {'end': 463.007, 'src': 'heatmap', 'start': 425.545, 'weight': 0.795, 'content': [{'end': 434.094, 'text': "the second case that i can think of is if i'm standing over here before moving to here, i should actually make this connection,", 'start': 425.545, 'duration': 8.549}, {'end': 438.354, 'text': 'make this yellow threaded, threaded path.', 'start': 434.094, 'duration': 4.26}, {'end': 442.216, 'text': 'why? because if you have once moved here, you cannot come back.', 'start': 438.354, 'duration': 3.862}, {'end': 444.558, 'text': 'so before moving you have to make this path.', 'start': 442.216, 'duration': 2.342}, {'end': 463.007, 'text': 'so can i say before moving left, yes, before going to left, can i say whichever is the right most guy, right most guy on left subtree,', 'start': 444.558, 'duration': 18.449}], 'summary': 'Before moving left, make a path to the rightmost guy on the left subtree.', 'duration': 37.462, 'max_score': 425.545, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r4425545.jpg'}], 'start': 38.314, 'title': 'Binary tree traversals', 'summary': 'Introduces morris traversal as a space-efficient alternative to recursive and iterative traversals, emphasizing its ability to achieve in-order and pre-order traversal using nearly o(n) time and no extra space. additionally, it explains the concept of inorder traversal for a binary tree and details the process of traversing the tree from left to right, highlighting the importance of backtracking and making connections to optimize the traversal process.', 'chapters': [{'end': 134.017, 'start': 38.314, 'title': 'Morris traversal explained', 'summary': 'Introduces morris traversal as a space-efficient alternative to recursive and iterative traversals, emphasizing its ability to achieve in-order and pre-order traversal using nearly o(n) time and no extra space, leveraging the concept of threaded binary tree.', 'duration': 95.703, 'highlights': ['Morris traversal achieves in-order and pre-order traversal with nearly O(n) time complexity and no extra space, making it more efficient than recursive and iterative traversals.', 'Morris traversal leverages the concept of threaded binary tree to achieve space efficiency and is highlighted for its ability to perform operations in O(n) time with no extra space consumption.', 'The chapter emphasizes on teaching the intuition behind Morris traversal and live coding to ensure a strong understanding and retention of the concept for the audience.']}, {'end': 529.657, 'start': 134.017, 'title': 'Binary tree inorder traversal', 'summary': 'Explains the concept of inorder traversal for a binary tree, detailing the process of traversing the tree from left to right, highlighting the importance of backtracking and making connections to optimize the traversal process.', 'duration': 395.64, 'highlights': ['The inorder traversal involves moving from left to root to right, with the left being 4 and the root being 2, and observing the backtracking process for efficient recursion.', 'The pattern of moving from the last node of any subtree back to the root is highlighted as a key observation for optimizing the traversal process.', 'The cases of traversal are discussed, including when the left is null, the connection of the rightmost node on the left subtree, and determining the movement to the right after coming back via threading.']}], 'duration': 491.343, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r438314.jpg', 'highlights': ['Morris traversal achieves in-order and pre-order traversal with nearly O(n) time complexity and no extra space, making it more efficient than recursive and iterative traversals.', 'The chapter emphasizes on teaching the intuition behind Morris traversal and live coding to ensure a strong understanding and retention of the concept for the audience.', 'The inorder traversal involves moving from left to root to right, with the left being 4 and the root being 2, and observing the backtracking process for efficient recursion.', 'The pattern of moving from the last node of any subtree back to the root is highlighted as a key observation for optimizing the traversal process.']}, {'end': 847.083, 'segs': [{'end': 593.506, 'src': 'embed', 'start': 559.098, 'weight': 2, 'content': [{'end': 560.599, 'text': 'okay, makes sense.', 'start': 559.098, 'duration': 1.501}, {'end': 561.62, 'text': 'what about the other?', 'start': 560.599, 'duration': 1.021}, {'end': 564.742, 'text': "once you have once i've removed the thread, now you can move right.", 'start': 561.62, 'duration': 3.122}, {'end': 565.863, 'text': 'so how did you determine?', 'start': 564.742, 'duration': 1.121}, {'end': 569.21, 'text': 'So the determination was very simple.', 'start': 567.389, 'duration': 1.821}, {'end': 577.794, 'text': 'What I said was, if the rightmost guy of the left sub-tree does not have a thread, so connect the thread.', 'start': 569.55, 'duration': 8.244}, {'end': 583.936, 'text': "Once you've connected the thread, move left so that afterwards you can actually come back directly to this guy.", 'start': 578.454, 'duration': 5.482}, {'end': 593.506, 'text': 'If on the rightmost there already exists a thread, there already exists a thread, then remove it and now you can say you will move to right.', 'start': 584.957, 'duration': 8.549}], 'summary': 'Algorithm determines thread connection based on rightmost node, enabling efficient movement.', 'duration': 34.408, 'max_score': 559.098, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r4559098.jpg'}, {'end': 658.238, 'src': 'embed', 'start': 631.238, 'weight': 5, 'content': [{'end': 636.942, 'text': 'so before going left if there is a left, if there is a left On this left subtree, take the rightmost guy.', 'start': 631.238, 'duration': 5.704}, {'end': 637.823, 'text': 'Take the last guy.', 'start': 637.022, 'duration': 0.801}, {'end': 639.744, 'text': 'The last guy is 6.', 'start': 638.243, 'duration': 1.501}, {'end': 640.705, 'text': 'Create the thread.', 'start': 639.744, 'duration': 0.961}, {'end': 642.086, 'text': 'Create the thread.', 'start': 641.245, 'duration': 0.841}, {'end': 643.947, 'text': "Perfect I've created the thread.", 'start': 642.746, 'duration': 1.201}, {'end': 646.349, 'text': "Once you've created the thread, then move.", 'start': 644.427, 'duration': 1.922}, {'end': 650.512, 'text': 'Nice After that, again you have to move to the left.', 'start': 647.65, 'duration': 2.862}, {'end': 658.238, 'text': "So, again you see on the left, who's the last right guy? So, you'll say, this is the only guy who will ultimately be the last guy.", 'start': 651.012, 'duration': 7.226}], 'summary': 'Thread creation and movement process involving finding the rightmost guy, creating the thread, and moving left.', 'duration': 27, 'max_score': 631.238, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r4631238.jpg'}, {'end': 851.644, 'src': 'embed', 'start': 825.749, 'weight': 0, 'content': [{'end': 831.231, 'text': 'i went to the left and i easily came back to the root using the threaded binary.', 'start': 825.749, 'duration': 5.482}, {'end': 833.892, 'text': 'uh, threaded uh, binary tree.', 'start': 831.231, 'duration': 2.661}, {'end': 835.113, 'text': 'so i was creating threads.', 'start': 833.892, 'duration': 1.221}, {'end': 837.073, 'text': 'just make sure you erase off threads.', 'start': 835.113, 'duration': 1.96}, {'end': 840.254, 'text': "don't leave the threads, okay, otherwise the binary tree will be wrong.", 'start': 837.073, 'duration': 3.181}, {'end': 841.415, 'text': 'so make sure you leave the threads.', 'start': 840.254, 'duration': 1.161}, {'end': 847.083, 'text': 'looks interesting, right, if I have these cases coded, I think I can do this.', 'start': 842.642, 'duration': 4.441}, {'end': 851.644, 'text': "so let's try to code it and again I'll show it how to code on life.", 'start': 847.083, 'duration': 4.561}], 'summary': 'Using threaded binary trees to navigate and create threads, ensuring threads are erased to maintain tree integrity.', 'duration': 25.895, 'max_score': 825.749, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r4825749.jpg'}], 'start': 529.657, 'title': 'Threaded binary trees', 'summary': 'Discusses operations for adding and removing threads in a threaded binary tree, emphasizing the importance of considering edge cases. it also explains the process of inorder traversal using a threaded binary tree, showcasing the steps involved and resulting in a clear understanding of the traversal process.', 'chapters': [{'end': 631.238, 'start': 529.657, 'title': 'Threaded binary tree operations', 'summary': 'Discusses the operations of adding and removing threads in a threaded binary tree, outlining the conditions and logic for each operation, and emphasizes the importance of considering edge cases in the implementation.', 'duration': 101.581, 'highlights': ['The chapter emphasizes the importance of considering edge cases in the implementation of adding and removing threads in a threaded binary tree. The speaker stresses the significance of considering edge cases in the implementation of adding and removing threads in a threaded binary tree, ensuring comprehensive coverage of potential scenarios.', 'The logic for adding and removing threads in the threaded binary tree is explained, including conditions based on the existence of threads at the rightmost node of the left sub-tree. The speaker explains the logic for adding and removing threads in the threaded binary tree, detailing conditions based on the existence of threads at the rightmost node of the left sub-tree, providing clarity on the decision-making process.', 'The speaker discusses the process of determining the movement after removing a thread in the threaded binary tree, emphasizing the simplicity of the determination process. The speaker outlines the process of determining the movement after removing a thread in the threaded binary tree, highlighting the simplicity of the determination process and the criteria for subsequent movements.']}, {'end': 847.083, 'start': 631.238, 'title': 'Inorder traversal with threaded binary tree', 'summary': 'Explains the process of inorder traversal using a threaded binary tree, showcasing the steps involved in creating threads, moving through subtrees, and determining traversal directions based on thread presence, resulting in a clear understanding of the inorder traversal process.', 'duration': 215.845, 'highlights': ['The process of creating threads in a threaded binary tree to facilitate inorder traversal, ensuring that threads are properly erased after use to maintain the integrity of the binary tree. The chapter emphasizes the importance of creating threads in a threaded binary tree to facilitate inorder traversal, with a caution to erase threads properly to avoid disrupting the binary tree structure.', 'Determining traversal directions based on the presence of threads, including cutting off links and moving to the appropriate subtree, showcasing the practical application of threaded binary tree concepts. The chapter demonstrates the practical application of threaded binary tree concepts by showcasing the process of determining traversal directions based on the presence of threads, including cutting off links and moving to the appropriate subtree.', 'Illustrating the steps involved in moving through subtrees, identifying the last node, and creating threads to facilitate efficient inorder traversal. The chapter illustrates the steps involved in moving through subtrees, identifying the last node, and creating threads to facilitate efficient inorder traversal, providing a clear understanding of the process.']}], 'duration': 317.426, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r4529657.jpg', 'highlights': ['The chapter emphasizes the importance of considering edge cases in adding and removing threads in a threaded binary tree.', 'The logic for adding and removing threads in the threaded binary tree is explained, including conditions based on the existence of threads at the rightmost node of the left sub-tree.', 'The speaker discusses the process of determining the movement after removing a thread in the threaded binary tree, emphasizing the simplicity of the determination process.', 'The chapter emphasizes the importance of creating threads in a threaded binary tree to facilitate inorder traversal, with a caution to erase threads properly to avoid disrupting the binary tree structure.', 'Determining traversal directions based on the presence of threads, including cutting off links and moving to the appropriate subtree, showcasing the practical application of threaded binary tree concepts.', 'Illustrating the steps involved in moving through subtrees, identifying the last node, and creating threads to facilitate efficient inorder traversal.']}, {'end': 1137.25, 'segs': [{'end': 927.144, 'src': 'embed', 'start': 898.851, 'weight': 3, 'content': [{'end': 900.751, 'text': 'so this guy itself is the root.', 'start': 898.851, 'duration': 1.9}, {'end': 901.632, 'text': 'so no left.', 'start': 900.751, 'duration': 0.881}, {'end': 903.312, 'text': 'so root will be printed right.', 'start': 901.632, 'duration': 1.68}, {'end': 907.574, 'text': "so let's take the root inorder.pushback again, java, people can do that.", 'start': 903.312, 'duration': 4.262}, {'end': 911.196, 'text': "uh, rls.add, i'll say curr.val will be added.", 'start': 907.574, 'duration': 3.622}, {'end': 912.916, 'text': "okay, so i'll add this.", 'start': 911.196, 'duration': 1.72}, {'end': 917.819, 'text': "once i've added this, can i say curr will move curr off right, perfect.", 'start': 912.916, 'duration': 4.903}, {'end': 919.179, 'text': "so i've done the first case.", 'start': 917.819, 'duration': 1.36}, {'end': 927.144, 'text': "can i say i've done the first case, which is left dot null print, which means i've taken it into the in order and after that i've moved right.", 'start': 919.179, 'duration': 7.965}], 'summary': 'The root will be printed, and the in-order traversal is performed in java.', 'duration': 28.293, 'max_score': 898.851, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r4898851.jpg'}, {'end': 989.312, 'src': 'embed', 'start': 942.453, 'weight': 0, 'content': [{'end': 943.893, 'text': "what did i do if i'm standing here?", 'start': 942.453, 'duration': 1.44}, {'end': 944.334, 'text': 'what did i do?', 'start': 943.893, 'duration': 0.441}, {'end': 952.583, 'text': 'basically went to the left subtree and figure out the last guy of the left subtree that will be visited in that in order.', 'start': 945.599, 'duration': 6.984}, {'end': 959.127, 'text': 'so can I say this is the last guy which will be visited in the in order of the left subtree, which ultimately means go to the left,', 'start': 952.583, 'duration': 6.544}, {'end': 962.149, 'text': 'go to the rightmost guy, go to the left, go to the rightmost guy.', 'start': 959.127, 'duration': 3.022}, {'end': 966.211, 'text': "so why don't I write that?", 'start': 962.149, 'duration': 4.062}, {'end': 974.788, 'text': "so I will say tree node, start previous and equal to, i'll go to the left, which is curve, left.", 'start': 966.211, 'duration': 8.577}, {'end': 976.368, 'text': 'a lot, move curve, very, very important.', 'start': 974.788, 'duration': 1.58}, {'end': 978.989, 'text': "now i'll go to as right as i can.", 'start': 976.368, 'duration': 2.621}, {'end': 983.05, 'text': 'if there exists a right, okay, if there exists a right, very important.', 'start': 978.989, 'duration': 4.061}, {'end': 989.312, 'text': 'if there exists a right and the right is not pointing to himself, that is also again very important.', 'start': 983.05, 'duration': 6.262}], 'summary': 'Traversed left subtree to find last visited node, then moved to the rightmost node. implemented logic for tree traversal.', 'duration': 46.859, 'max_score': 942.453, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r4942453.jpg'}, {'end': 1042.036, 'src': 'embed', 'start': 1012.073, 'weight': 1, 'content': [{'end': 1013.374, 'text': 'Tell the guy who has the last right.', 'start': 1012.073, 'duration': 1.301}, {'end': 1014.275, 'text': "So, I've moved it.", 'start': 1013.754, 'duration': 0.521}, {'end': 1019.879, 'text': 'Okay Now, what are the cases? The first case will be if this right will come null.', 'start': 1014.315, 'duration': 5.564}, {'end': 1021.12, 'text': "That's the first case.", 'start': 1020.159, 'duration': 0.961}, {'end': 1026.124, 'text': 'So, I can say the first case will be if the right comes out to be null.', 'start': 1021.601, 'duration': 4.523}, {'end': 1027.425, 'text': "Okay That's the first case.", 'start': 1026.284, 'duration': 1.141}, {'end': 1028.566, 'text': 'What will be the other case?', 'start': 1027.826, 'duration': 0.74}, {'end': 1031.888, 'text': "The other case can be when you're doing a pre-order.", 'start': 1028.986, 'duration': 2.902}, {'end': 1037.233, 'text': 'this guy is having a thread where he said previous right is pointing to the curve.', 'start': 1031.888, 'duration': 5.345}, {'end': 1039.234, 'text': 'Previous right is pointing to the curve.', 'start': 1037.693, 'duration': 1.541}, {'end': 1040.035, 'text': 'That can be the other case.', 'start': 1039.275, 'duration': 0.76}, {'end': 1040.695, 'text': 'Okay Perfect.', 'start': 1040.194, 'duration': 0.501}, {'end': 1042.036, 'text': 'So, there can be two places.', 'start': 1041.016, 'duration': 1.02}], 'summary': 'Discussion about two cases regarding null and pre-order, for a total of two cases.', 'duration': 29.963, 'max_score': 1012.073, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r41012073.jpg'}, {'end': 1102.018, 'src': 'heatmap', 'start': 1046.637, 'weight': 2, 'content': [{'end': 1054.001, 'text': "I will say previous right, instead of pointing to null, why don't we create the thread? And the thread will be pointing to curve.", 'start': 1046.637, 'duration': 7.364}, {'end': 1059.063, 'text': 'Correct? So, I have made sure that 6 is pointing to curve.', 'start': 1054.441, 'duration': 4.622}, {'end': 1063.805, 'text': 'Perfect Now, once I have done that, can I say, now I will do my traversing.', 'start': 1059.503, 'duration': 4.302}, {'end': 1069.857, 'text': "Nice So what I'll do is, after this, I'll move the curve to here.", 'start': 1066.735, 'duration': 3.122}, {'end': 1072.058, 'text': 'And again, same thing will happen.', 'start': 1070.557, 'duration': 1.501}, {'end': 1073.819, 'text': 'This will create a thread.', 'start': 1072.579, 'duration': 1.24}, {'end': 1075.42, 'text': 'And after that, curve will move.', 'start': 1074.26, 'duration': 1.16}, {'end': 1079.763, 'text': 'Okay This time, when curve tries to move, it again comes back.', 'start': 1075.941, 'duration': 3.822}, {'end': 1086.407, 'text': 'So again, when it comes back over here, Again, when it tries to find force right and it points to 2.', 'start': 1080.243, 'duration': 6.164}, {'end': 1087.948, 'text': 'This is the case when this will be happening.', 'start': 1086.407, 'duration': 1.541}, {'end': 1089.83, 'text': 'Okay So, this time it will come to else.', 'start': 1088.089, 'duration': 1.741}, {'end': 1096.954, 'text': 'When this time it comes back to else, what do you need to do? What do you need to do? Force right is still pointing to curve.', 'start': 1090.41, 'duration': 6.544}, {'end': 1102.018, 'text': 'So, can I say the previous right is no more.', 'start': 1097.495, 'duration': 4.523}], 'summary': 'Created thread, 6 points to curve, force right points to 2.', 'duration': 27.182, 'max_score': 1046.637, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r41046637.jpg'}], 'start': 847.083, 'title': 'Tree traversal', 'summary': 'Explains in-order traversal and threaded binary tree traversal, focusing on handling left and right subtrees, edge cases, creating threads, and demonstrating the traversal process with examples.', 'chapters': [{'end': 962.149, 'start': 847.083, 'title': 'Inorder traversal function explanation', 'summary': 'Explains the process of performing an in-order traversal on a tree with a focus on handling left and right subtrees, emphasizing the edge cases and the actions taken in each case.', 'duration': 115.066, 'highlights': ['The chapter explains the process of performing an in-order traversal on a tree with a focus on handling left and right subtrees, emphasizing the edge cases and the actions taken in each case.', 'The narrator describes the process of traversing a tree in an in-order manner, discussing the scenarios where the left subtree is null and when it is not null.', 'The speaker outlines the actions taken when the left subtree is null, emphasizing the addition of the root value to the in-order list and moving to the right subtree.', 'The explanation delves into the scenario where the left subtree is not null, highlighting the process of navigating to the rightmost node of the left subtree.', 'The speaker provides a detailed breakdown of the steps involved in navigating through the left subtree to identify the last node to be visited in the in-order traversal.']}, {'end': 1137.25, 'start': 962.149, 'title': 'Threaded binary tree traversal', 'summary': 'Explains the process of creating and traversing a threaded binary tree, emphasizing the importance of handling cases where the right node is null or when creating a thread is necessary, and demonstrating the traversal process with specific examples.', 'duration': 175.101, 'highlights': ['Handling cases where the right node is null or creating a thread is necessary The chapter emphasizes the importance of handling cases where the right node is null or creating a thread is necessary in a threaded binary tree.', 'Demonstrating the traversal process with specific examples The chapter provides specific examples to demonstrate the threaded binary tree traversal process, illustrating the movement of nodes and the creation of threads.', 'Emphasizing the importance of moving to the extreme right in the traversal process The chapter highlights the significance of moving to the extreme right during the traversal process in a threaded binary tree.']}], 'duration': 290.167, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r4847083.jpg', 'highlights': ['The chapter explains the process of performing an in-order traversal on a tree with a focus on handling left and right subtrees, emphasizing the edge cases and the actions taken in each case.', 'The chapter emphasizes the importance of handling cases where the right node is null or creating a thread is necessary in a threaded binary tree.', 'The chapter provides specific examples to demonstrate the threaded binary tree traversal process, illustrating the movement of nodes and the creation of threads.', 'The speaker outlines the actions taken when the left subtree is null, emphasizing the addition of the root value to the in-order list and moving to the right subtree.', 'The chapter highlights the significance of moving to the extreme right during the traversal process in a threaded binary tree.']}, {'end': 1421.601, 'segs': [{'end': 1206.476, 'src': 'embed', 'start': 1137.25, 'weight': 0, 'content': [{'end': 1141.151, 'text': "this is once you visit the root, and this is the other time, you'll visit the root.", 'start': 1137.25, 'duration': 3.901}, {'end': 1145.553, 'text': 'okay, for this guy four, he himself will be the root, so it will automatically be taken.', 'start': 1141.151, 'duration': 4.402}, {'end': 1156.638, 'text': 'so this is how a simple, modest traversal code might look like and you can simply return the in order traversal.', 'start': 1145.553, 'duration': 11.085}, {'end': 1159.379, 'text': "so guys, uh, i've almost explained everything.", 'start': 1156.638, 'duration': 2.741}, {'end': 1165.911, 'text': "i've written the code order to get a much further clarity, i highly recommend take, uh,", 'start': 1159.379, 'duration': 6.532}, {'end': 1173.123, 'text': 'two or three more binary trees and keep a dry run on this so that the idea of thread gets, uh, further clarified.', 'start': 1165.911, 'duration': 7.212}, {'end': 1178.676, 'text': 'okay, Now the question is, what if I change it to pre-order?', 'start': 1173.123, 'duration': 5.553}, {'end': 1184.28, 'text': 'How will the question be solved for something which is a pre-order traversal?', 'start': 1179.156, 'duration': 5.124}, {'end': 1190.144, 'text': 'Because I said in the beginning that if you can learn in order, the pre-order will be a shuttle one line change.', 'start': 1184.3, 'duration': 5.844}, {'end': 1192.906, 'text': 'So just think, just think what can be.', 'start': 1190.584, 'duration': 2.322}, {'end': 1195.908, 'text': "What am I doing? I'm doing left route traversal.", 'start': 1193.346, 'duration': 2.562}, {'end': 1198.43, 'text': 'right on in order, okay.', 'start': 1196.568, 'duration': 1.862}, {'end': 1200.852, 'text': "so ideally what i'm doing is i'm printing the roots.", 'start': 1198.43, 'duration': 2.422}, {'end': 1206.476, 'text': "whenever i'm reaching the root, i'm printing it like for an example, the thread brought me back to this root.", 'start': 1200.852, 'duration': 5.624}], 'summary': 'Explanation of binary tree traversal and recommendation to practice on 2-3 trees for clarity.', 'duration': 69.226, 'max_score': 1137.25, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r41137250.jpg'}, {'end': 1311.954, 'src': 'embed', 'start': 1286.601, 'weight': 1, 'content': [{'end': 1294.087, 'text': 'Yes, I just did a one liner change and the in order was converted into a pre-order traversal because I just have to place route at front.', 'start': 1286.601, 'duration': 7.486}, {'end': 1296.509, 'text': "When you're starting the visit, just visit it.", 'start': 1294.528, 'duration': 1.981}, {'end': 1298.931, 'text': "When you come back via thread, there's no need to visit.", 'start': 1297.23, 'duration': 1.701}, {'end': 1299.552, 'text': 'Just go right.', 'start': 1298.971, 'duration': 0.581}, {'end': 1300.272, 'text': 'Simple as that.', 'start': 1299.792, 'duration': 0.48}, {'end': 1302.414, 'text': 'No need to take it into your pre-order.', 'start': 1300.532, 'duration': 1.882}, {'end': 1305.891, 'text': 'how the uh pre-order code will look like.', 'start': 1303.51, 'duration': 2.381}, {'end': 1311.954, 'text': "so guys, uh, if i talk about the time complexity, since, uh, at every time, like whenever you're over here,", 'start': 1305.891, 'duration': 6.063}], 'summary': 'One-liner change converts in-order to pre-order traversal, simplifying code and improving efficiency.', 'duration': 25.353, 'max_score': 1286.601, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r41286601.jpg'}, {'end': 1399.561, 'src': 'embed', 'start': 1360.057, 'weight': 2, 'content': [{'end': 1363.919, 'text': 'when i say amortize, it means one plus two, plus one plus.', 'start': 1360.057, 'duration': 3.862}, {'end': 1366.44, 'text': 'all the iterations together will make it big.', 'start': 1363.919, 'duration': 2.521}, {'end': 1375.383, 'text': 'often this, all this while loop throughout will run for n like not and on individual terms, in total will run for n.', 'start': 1366.44, 'duration': 8.943}, {'end': 1382.569, 'text': "so can i say uh, in total this while loop will run for n and since i'm traversing all nodes, i'm running for big of n.", 'start': 1375.383, 'duration': 7.186}, {'end': 1384.99, 'text': "furthermore, so it's near about again.", 'start': 1382.569, 'duration': 2.421}, {'end': 1388.113, 'text': "it's not exactly when it's near about.", 'start': 1384.99, 'duration': 3.123}, {'end': 1390.915, 'text': 'uh, we go of n time complexity, if i summarize that.', 'start': 1388.113, 'duration': 2.802}, {'end': 1396.719, 'text': 'but the important thing is the space complexity taken is big of one, which is indeed our main point.', 'start': 1390.915, 'duration': 5.804}, {'end': 1399.561, 'text': "So I hope you've understood the entire explanation as well as the code.", 'start': 1397.159, 'duration': 2.402}], 'summary': 'The while loop runs for n iterations, resulting in a time complexity of o(n), with a space complexity of o(1).', 'duration': 39.504, 'max_score': 1360.057, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r41360057.jpg'}], 'start': 1137.25, 'title': 'Binary tree traversal and time complexity', 'summary': 'Delves into explaining in-order and pre-order traversal of binary trees, with a simple traversal code explained. it also explains time complexity as amortized n complexity with space complexity of big o(1).', 'chapters': [{'end': 1305.891, 'start': 1137.25, 'title': 'Binary tree traversal explanation', 'summary': 'Delves into explaining in-order and pre-order traversal of binary trees, with a simple traversal code explained and a one-liner change converting in-order to pre-order traversal.', 'duration': 168.641, 'highlights': ['The chapter explains the concept of in-order traversal and provides a simple traversal code for better understanding.', 'It is recommended to perform dry runs on multiple binary trees to understand the concept of thread further.', 'The discussion shifts to converting in-order traversal to pre-order traversal with a one-liner change, simplifying the process.', 'The explanation highlights the transformation of in-order traversal to pre-order traversal by placing the root at the front during the visit.']}, {'end': 1421.601, 'start': 1305.891, 'title': 'Time complexity and space complexity explanation', 'summary': 'Explains the time complexity as amortized n complexity with space complexity of big o(1), and the while loop throughout will run for n, with the important thing being the space complexity taken is big o(1).', 'duration': 115.71, 'highlights': ['The time complexity is amortized n complexity with space complexity of big O(1). The speaker explains that the time complexity is amortized n complexity with the space complexity taken as big O(1), emphasizing the efficiency of the algorithm.', 'The while loop throughout will run for n. It is mentioned that the while loop will run for n, highlighting the iteration process and the impact on time complexity.', 'The space complexity taken is big O(1). The importance of the space complexity being big O(1) is emphasized, indicating the efficient use of space in the algorithm.']}], 'duration': 284.351, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/80Zug6D1_r4/pics/80Zug6D1_r41137250.jpg', 'highlights': ['The chapter explains in-order traversal and provides a simple traversal code.', 'The discussion shifts to converting in-order traversal to pre-order traversal with a one-liner change.', 'The time complexity is amortized n with space complexity of big O(1).', 'The explanation highlights the transformation of in-order traversal to pre-order traversal by placing the root at the front during the visit.', 'The while loop throughout will run for n, emphasizing the iteration process and the impact on time complexity.', 'It is recommended to perform dry runs on multiple binary trees to understand the concept of thread further.', 'The space complexity taken is big O(1), indicating the efficient use of space in the algorithm.']}], 'highlights': ["Releval by Anacademy is India's first hiring platform that can get you a job within a week itself, with top companies and unicorns, by registering for their test.", "The Releval test can schedule your interview within a week with India's top companies and budding unicorns.", 'Releval test is highlighted as free to apply, providing a potential solution to the lengthy job application process.', 'Morris traversal achieves in-order and pre-order traversal with nearly O(n) time complexity and no extra space, making it more efficient than recursive and iterative traversals.', 'The chapter emphasizes on teaching the intuition behind Morris traversal and live coding to ensure a strong understanding and retention of the concept for the audience.', 'The inorder traversal involves moving from left to root to right, with the left being 4 and the root being 2, and observing the backtracking process for efficient recursion.', 'The pattern of moving from the last node of any subtree back to the root is highlighted as a key observation for optimizing the traversal process.', 'The chapter emphasizes the importance of considering edge cases in adding and removing threads in a threaded binary tree.', 'The logic for adding and removing threads in the threaded binary tree is explained, including conditions based on the existence of threads at the rightmost node of the left sub-tree.', 'The speaker discusses the process of determining the movement after removing a thread in the threaded binary tree, emphasizing the simplicity of the determination process.', 'The chapter emphasizes the importance of creating threads in a threaded binary tree to facilitate inorder traversal, with a caution to erase threads properly to avoid disrupting the binary tree structure.', 'Determining traversal directions based on the presence of threads, including cutting off links and moving to the appropriate subtree, showcasing the practical application of threaded binary tree concepts.', 'Illustrating the steps involved in moving through subtrees, identifying the last node, and creating threads to facilitate efficient inorder traversal.', 'The chapter explains the process of performing an in-order traversal on a tree with a focus on handling left and right subtrees, emphasizing the edge cases and the actions taken in each case.', 'The chapter emphasizes the importance of handling cases where the right node is null or creating a thread is necessary in a threaded binary tree.', 'The chapter provides specific examples to demonstrate the threaded binary tree traversal process, illustrating the movement of nodes and the creation of threads.', 'The speaker outlines the actions taken when the left subtree is null, emphasizing the addition of the root value to the in-order list and moving to the right subtree.', 'The chapter highlights the significance of moving to the extreme right during the traversal process in a threaded binary tree.', 'The chapter explains in-order traversal and provides a simple traversal code.', 'The discussion shifts to converting in-order traversal to pre-order traversal with a one-liner change.', 'The time complexity is amortized n with space complexity of big O(1).', 'The explanation highlights the transformation of in-order traversal to pre-order traversal by placing the root at the front during the visit.', 'The while loop throughout will run for n, emphasizing the iteration process and the impact on time complexity.', 'It is recommended to perform dry runs on multiple binary trees to understand the concept of thread further.', 'The space complexity taken is big O(1), indicating the efficient use of space in the algorithm.']}