title

L38. Flatten a Binary Tree to Linked List | 3 Approaches | 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': 'L38. Flatten a Binary Tree to Linked List | 3 Approaches | C++ | Java', 'heatmap': [{'end': 358.33, 'start': 274.567, 'weight': 0.821}, {'end': 435.237, 'start': 419.481, 'weight': 0.723}, {'end': 616.74, 'start': 589.36, 'weight': 0.72}, {'end': 673.725, 'start': 641.326, 'weight': 0.788}, {'end': 1142.103, 'start': 1044.579, 'weight': 0.713}], 'summary': 'Discusses releval by unacademy, a hiring platform for freshers, and explores flattening a binary tree into a linked list using various approaches such as recursive solution, reverse post order traversal, and stack-based method, aiming to achieve specific node arrangements and improve algorithm efficiency.', 'chapters': [{'end': 30.721, 'segs': [{'end': 42.863, 'src': 'embed', 'start': 14.332, 'weight': 0, 'content': [{'end': 20.434, 'text': "Releval by Unacademy is a hiring platform that helps freshers and experienced people to get jobs in India's top companies.", 'start': 14.332, 'duration': 6.102}, {'end': 21.654, 'text': 'All you need is skills.', 'start': 20.574, 'duration': 1.08}, {'end': 26.057, 'text': 'So what you need to do is you just need to give the relevant test that is completely based on your skills.', 'start': 22.034, 'duration': 4.023}, {'end': 30.721, 'text': 'Depending on your performance, your interview will be scheduled and you will be hired from the relevant platform.', 'start': 26.217, 'duration': 4.504}, {'end': 33.082, 'text': "And the best thing about this is it's absolutely free.", 'start': 30.941, 'duration': 2.141}, {'end': 35.945, 'text': 'So what are you waiting for? Please make sure you check out the links in the description.', 'start': 33.102, 'duration': 2.843}, {'end': 42.863, 'text': 'hey, everyone, welcome back to the channel.', 'start': 41.482, 'duration': 1.381}], 'summary': 'Releval by unacademy is a free hiring platform for freshers and experienced individuals in india, based on skills.', 'duration': 28.531, 'max_score': 14.332, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR414332.jpg'}], 'start': 0.029, 'title': 'Releval: job opportunities for freshers', 'summary': 'Discusses releval by unacademy, a hiring platform enabling freshers and experienced individuals to secure jobs in top indian companies based on their skills and performance.', 'chapters': [{'end': 30.721, 'start': 0.029, 'title': 'Releval: job opportunities for freshers', 'summary': 'Discusses releval by unacademy, a hiring platform that helps freshers and experienced individuals secure jobs in top indian companies like cred, upgrad, urban company, and razorpay solely based on their skills and performance.', 'duration': 30.692, 'highlights': ["Releval by Unacademy is a hiring platform that helps freshers and experienced people to get jobs in India's top companies.", 'Companies like CRED, UpGrad, Urban Company, Razorpay are accessible through Releval by Unacademy.', 'Candidates are hired based solely on their skills and performance in the relevant test.']}], 'duration': 30.692, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR429.jpg', 'highlights': ['Releval by Unacademy is a hiring platform for freshers and experienced individuals in top Indian companies.', 'Companies like CRED, UpGrad, Urban Company, Razorpay are accessible through Releval by Unacademy.', 'Candidates are hired based solely on their skills and performance in the relevant test.']}, {'end': 258.175, 'segs': [{'end': 84.79, 'src': 'embed', 'start': 54.153, 'weight': 0, 'content': [{'end': 56.915, 'text': 'but uh, it is tough, it is tough.', 'start': 54.153, 'duration': 2.762}, {'end': 61.639, 'text': "now let me tell you how do you need to flatten it, and then i'll tell you why it is tough.", 'start': 56.915, 'duration': 4.724}, {'end': 63.281, 'text': 'so basically, uh, what do you need to do?', 'start': 61.639, 'duration': 1.642}, {'end': 66.804, 'text': 'is you need to make this a linked list into something like this?', 'start': 63.281, 'duration': 3.523}, {'end': 69.086, 'text': 'okay, like a linked list like this?', 'start': 66.804, 'duration': 2.282}, {'end': 84.79, 'text': "So if you write down the pre-order of this, it's going to be 1, 2, 3, and then a 4, then a 5, then a 6, then a 7..", 'start': 76.468, 'duration': 8.322}], 'summary': 'The challenge is to flatten a linked list into a specific order.', 'duration': 30.637, 'max_score': 54.153, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR454153.jpg'}, {'end': 246.595, 'src': 'embed', 'start': 217.585, 'weight': 1, 'content': [{'end': 221.188, 'text': "so it's kind of a right, then a left, then then i'll work with the upper guys.", 'start': 217.585, 'duration': 3.603}, {'end': 224.01, 'text': 'perfect, So right left root.', 'start': 221.188, 'duration': 2.822}, {'end': 224.89, 'text': "It's not a post order.", 'start': 224.19, 'duration': 0.7}, {'end': 225.59, 'text': "It's not an in order.", 'start': 224.91, 'duration': 0.68}, {'end': 226.41, 'text': "It's not a pre order.", 'start': 225.63, 'duration': 0.78}, {'end': 228.071, 'text': "It's kind of a reverse post order.", 'start': 226.43, 'duration': 1.641}, {'end': 230.851, 'text': 'You can call it reverse post order if you want to.', 'start': 228.111, 'duration': 2.74}, {'end': 234.072, 'text': 'So this is what my thought process will be.', 'start': 231.371, 'duration': 2.701}, {'end': 241.994, 'text': "I'll try to do a reverse post order kind of a thing and try to first attach 7 to 6 and then probably 4 to 5 and so on.", 'start': 234.152, 'duration': 7.842}, {'end': 243.634, 'text': 'That is what my thinking will be.', 'start': 242.034, 'duration': 1.6}, {'end': 246.595, 'text': "Okay, so let's see how I can do that.", 'start': 244.094, 'duration': 2.501}], 'summary': 'Planning to use reverse post order to attach nodes in a specific sequence.', 'duration': 29.01, 'max_score': 217.585, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR4217585.jpg'}], 'start': 30.941, 'title': 'Flattening binary tree', 'summary': 'Discusses the challenging task of flattening a binary tree into a linked list, explaining the process and the recursive solution required, emphasizing the need to rearrange the nodes to achieve the desired structure. it also explores using a reverse post order traversal approach to rearrange and attach nodes in a tree, aiming to achieve a specific sequence of node arrangements, which can potentially improve the efficiency of the algorithm.', 'chapters': [{'end': 148.808, 'start': 30.941, 'title': 'Flatten binary tree to linked list', 'summary': 'Discusses the challenging task of flattening a binary tree into a linked list, explaining the process and the recursive solution required, emphasizing the need to rearrange the nodes to achieve the desired structure.', 'duration': 117.867, 'highlights': ['The process of flattening a binary tree into a linked list is explained, emphasizing the rearrangement of nodes to represent the pre-order of the binary tree as the linked list.', 'The difficulty of the task is highlighted, debunking the misconception of creating a new linked list and emphasizing the need to rearrange the existing nodes to achieve the desired structure.', 'The recursive solution required to solve the problem is discussed, providing insights into the approach needed to rearrange the tree nodes to flatten it into a linked list.']}, {'end': 258.175, 'start': 149.288, 'title': 'Reverse post order traversal approach', 'summary': 'Discusses using a reverse post order traversal approach to rearrange and attach nodes in a tree, aiming to achieve a specific sequence of node arrangements, which can potentially improve the efficiency of the algorithm.', 'duration': 108.887, 'highlights': ['Implementing a reverse post order traversal to rearrange and attach nodes in a tree can improve the efficiency of the algorithm. By using a reverse post order traversal, the algorithm aims to achieve a specific sequence of node arrangements, potentially improving efficiency.', 'Describing the logical solution as right left root, which is a reverse post order traversal approach. The logical solution is described as a right left root approach, which is essentially a reverse post order traversal.', 'Proposing a recursive code based on the reverse post order traversal approach. A piece of recursive code is proposed to work with the reverse post order traversal approach, indicating a practical implementation of the discussed concept.']}], 'duration': 227.234, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR430941.jpg', 'highlights': ['The process of flattening a binary tree into a linked list is explained, emphasizing the rearrangement of nodes to represent the pre-order of the binary tree as the linked list.', 'Implementing a reverse post order traversal to rearrange and attach nodes in a tree can improve the efficiency of the algorithm. By using a reverse post order traversal, the algorithm aims to achieve a specific sequence of node arrangements, potentially improving efficiency.']}, {'end': 634.562, 'segs': [{'end': 381.313, 'src': 'heatmap', 'start': 274.567, 'weight': 3, 'content': [{'end': 275.788, 'text': "So that's where I start off with.", 'start': 274.567, 'duration': 1.221}, {'end': 278.75, 'text': 'and then i go to the right.', 'start': 276.548, 'duration': 2.202}, {'end': 280.611, 'text': "so that's that's where i go right.", 'start': 278.75, 'duration': 1.861}, {'end': 284.294, 'text': 'then i again come back and i again go to the right perfect.', 'start': 280.611, 'duration': 3.683}, {'end': 286.995, 'text': 'then i again come back, go to the right and i find a null.', 'start': 284.294, 'duration': 2.701}, {'end': 287.996, 'text': "so i'll return.", 'start': 286.995, 'duration': 1.001}, {'end': 290.338, 'text': 'so when i return, the right is done.', 'start': 287.996, 'duration': 2.342}, {'end': 292.92, 'text': "so i'll go to node dot left.", 'start': 290.338, 'duration': 2.582}, {'end': 294.541, 'text': 'so this is where i go no dot left.', 'start': 292.92, 'duration': 1.621}, {'end': 298.838, 'text': 'now this one has no right, no left.', 'start': 295.177, 'duration': 3.661}, {'end': 304.74, 'text': "so i can say uh, when i, when i'm at seven, the right is null, the left is nine.", 'start': 298.838, 'duration': 5.902}, {'end': 306.24, 'text': 'so notes right.', 'start': 304.74, 'duration': 1.5}, {'end': 308.421, 'text': 'notes right should be pointing to previous.', 'start': 306.24, 'duration': 2.181}, {'end': 314.324, 'text': 'so notes right is pointing to null and notes left should also be pointing to null.', 'start': 308.421, 'duration': 5.903}, {'end': 315.906, 'text': 'why is notes right pointing to null?', 'start': 314.324, 'duration': 1.582}, {'end': 320.029, 'text': 'because previous is initialized as null, perfect.', 'start': 315.906, 'duration': 4.123}, {'end': 327.796, 'text': 'so since i did not need to do any modification, i made it as like this now, okay, so once they have been pointed to null,', 'start': 320.029, 'duration': 7.767}, {'end': 331.159, 'text': "it's time that previous should be updated with seven.", 'start': 327.796, 'duration': 3.363}, {'end': 333.841, 'text': 'so please update previous with seven.', 'start': 331.159, 'duration': 2.682}, {'end': 335.542, 'text': "now, what's the next step that you'll do?", 'start': 333.841, 'duration': 1.701}, {'end': 341.525, 'text': '6 digits right right, 6 digits left.', 'start': 336.883, 'duration': 4.642}, {'end': 343.325, 'text': '6 will perform these.', 'start': 341.525, 'duration': 1.8}, {'end': 344.506, 'text': 'see 6 does words.', 'start': 343.325, 'duration': 1.181}, {'end': 349.327, 'text': '6 says my right will be connected to previous.', 'start': 344.506, 'duration': 4.821}, {'end': 350.568, 'text': 'that is 7.', 'start': 349.327, 'duration': 1.241}, {'end': 352.008, 'text': 'that is 7.', 'start': 350.568, 'duration': 1.44}, {'end': 358.33, 'text': 'so 6 right is connected to this node itself and nodes left is now null.', 'start': 352.008, 'duration': 6.322}, {'end': 362.112, 'text': 'so it says it will be null now.', 'start': 358.33, 'duration': 3.782}, {'end': 366.74, 'text': 'so if I just erase it, this is nothing but null, Perfect.', 'start': 362.112, 'duration': 4.628}, {'end': 370.464, 'text': "After that, I'm saying previous is 6.", 'start': 367.981, 'duration': 2.483}, {'end': 372.946, 'text': 'So I updated previous to 6.', 'start': 370.464, 'duration': 2.482}, {'end': 374.047, 'text': 'So understand what I did.', 'start': 372.946, 'duration': 1.101}, {'end': 381.313, 'text': 'Since I was doing a traversal of right and left, the moment 7 was completed, I stored 7 in previous.', 'start': 374.607, 'duration': 6.706}], 'summary': 'Traversing and updating nodes in a binary tree, with specific pointers and values being modified and stored.', 'duration': 30.745, 'max_score': 274.567, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR4274567.jpg'}, {'end': 451.503, 'src': 'heatmap', 'start': 419.481, 'weight': 0.723, 'content': [{'end': 422.325, 'text': 'Now when you go to the left, you are at 2.', 'start': 419.481, 'duration': 2.844}, {'end': 424.288, 'text': 'So right is done, left is still waiting.', 'start': 422.325, 'duration': 1.963}, {'end': 426.311, 'text': "2s, you'll go to the right.", 'start': 425.31, 'duration': 1.001}, {'end': 429.596, 'text': "This guy doesn't have a right, doesn't have a left.", 'start': 427.335, 'duration': 2.261}, {'end': 432.116, 'text': 'So no more going into the flat and flat.', 'start': 429.876, 'duration': 2.24}, {'end': 435.237, 'text': 'So this guy will now say, my right will be previous.', 'start': 432.837, 'duration': 2.4}, {'end': 437.918, 'text': 'So this is the last guy that you completed for.', 'start': 435.657, 'duration': 2.261}, {'end': 439.418, 'text': "I hope you're getting the intuition.", 'start': 438.358, 'duration': 1.06}, {'end': 443.84, 'text': 'This is the last guy for which you completed the entire post order.', 'start': 440.219, 'duration': 3.621}, {'end': 451.503, 'text': "So what he'll do is he'll say, okay, why did you go and attach it? So, notes right went in and attached to 5.", 'start': 444.62, 'duration': 6.883}], 'summary': 'Completing the last guy in the post order, attaching to 5.', 'duration': 32.022, 'max_score': 419.481, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR4419481.jpg'}, {'end': 616.74, 'src': 'heatmap', 'start': 540.022, 'weight': 0, 'content': [{'end': 541.984, 'text': "The next time the previous will be 1 and it's over.", 'start': 540.022, 'duration': 1.962}, {'end': 548.17, 'text': 'Ultimately, if you rewrite this, this is equivalent to saying once write points to 2, 2 points to 3, 3 points to 4, 4 points to 5,', 'start': 542.404, 'duration': 5.766}, {'end': 550.193, 'text': 'then to 6 and then to 7, and so on.', 'start': 548.17, 'duration': 2.023}, {'end': 564.563, 'text': 'correct. so what i did was very simple the guys whose post order was completed i stored in previous and whenever i went to that i just attached it.', 'start': 554.718, 'duration': 9.845}, {'end': 565.944, 'text': 'i just attach it to that.', 'start': 564.563, 'duration': 1.381}, {'end': 566.644, 'text': "that's it.", 'start': 565.944, 'duration': 0.7}, {'end': 569.586, 'text': 'that is what i did using these couple of lines.', 'start': 566.644, 'duration': 2.942}, {'end': 574.969, 'text': 'i attached it to the previous guy whose reverse post order was completed and i made sure there was no.', 'start': 569.586, 'duration': 5.383}, {'end': 575.829, 'text': 'no left.', 'start': 574.969, 'duration': 0.86}, {'end': 585.678, 'text': 'left out two lines and i, since right and left calls are over for node, I said this guy is the new guy whose reverse post order is completed.', 'start': 575.829, 'duration': 9.849}, {'end': 586.338, 'text': "That's it.", 'start': 586.018, 'duration': 0.32}, {'end': 587.419, 'text': "That's as simple as that.", 'start': 586.378, 'duration': 1.041}, {'end': 589.08, 'text': "What's the time complexity?", 'start': 588.159, 'duration': 0.921}, {'end': 594.983, 'text': 'The time complexity stands out to be b go of n, and the space complexity also stands out to be b go of n.', 'start': 589.36, 'duration': 5.623}, {'end': 599.025, 'text': 'assuming the worst height is b go of n.', 'start': 594.983, 'duration': 4.042}, {'end': 601.426, 'text': "That's about the recursive solution.", 'start': 599.025, 'duration': 2.401}, {'end': 607.349, 'text': "So the second solution that I'll be discussing will be an iterative solution that uses a stack.", 'start': 602.383, 'duration': 4.966}, {'end': 610.272, 'text': "Now you don't need to tell this in the interview, just know this.", 'start': 607.629, 'duration': 2.643}, {'end': 612.615, 'text': "And again, I've written the code.", 'start': 610.893, 'duration': 1.722}, {'end': 616.74, 'text': "I'll be telling you the intuition while explaining the code so that it gets more clear.", 'start': 612.956, 'duration': 3.784}], 'summary': 'Implemented a recursive and iterative solution with time and space complexity of o(n).', 'duration': 72.593, 'max_score': 540.022, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR4540022.jpg'}], 'start': 258.334, 'title': 'Binary tree traversal', 'summary': 'Explains traversing, updating nodes, and completing post-order traversal of a binary tree, including reverse post order traversal algorithm with o(n) time complexity and o(n) space complexity.', 'chapters': [{'end': 381.313, 'start': 258.334, 'title': 'Binary tree code explanation', 'summary': 'Explains the code for traversing a binary tree and updating the previous and next nodes, demonstrating the intuition behind the process.', 'duration': 122.979, 'highlights': ["The code explanation for traversing a binary tree involves initializing 'previous' as null, traversing the nodes, updating 'previous' and connecting 'right' and 'left' nodes with 'previous' and 'null'.", 'The speaker emphasizes the importance of understanding the code flow before comprehending the intuition, ensuring seamless connection and comprehension.', "Detailed explanation of updating 'previous' and connecting 'right' and 'left' nodes, providing a clear understanding of the traversal process and the connections between nodes."]}, {'end': 452.544, 'start': 381.854, 'title': 'Binary tree traversal explanation', 'summary': 'Explains the process of completing post-order traversal of a binary tree, highlighting the steps involved in updating pointers while traversing through the nodes.', 'duration': 70.69, 'highlights': ['The last node completed for post-order traversal will update its pointers to connect with the previous nodes, demonstrating the completion of the traversal process.', "The process involves updating pointers and assigning new values to 'previous' as the traversal progresses through the binary tree.", 'The explanation emphasizes the simplicity of the process, ensuring a clear understanding of how the pointers are updated and connected during post-order traversal.']}, {'end': 634.562, 'start': 453.085, 'title': 'Reverse post order traversal', 'summary': 'Explains a reverse post order traversal algorithm for a tree, detailing the iterative and recursive solutions, with a time complexity of o(n) and space complexity of o(n.', 'duration': 181.477, 'highlights': ['The algorithm involves storing the nodes whose reverse post order traversal is completed and then attaching the nodes to the previous node, resulting in a time complexity of O(n) and space complexity of O(n).', 'The iterative solution involves using a stack to store the nodes in a last in first out manner, extending the concept of recursion and demonstrating a time complexity of O(n) and space complexity of O(n).', 'The explanation emphasizes the simplicity of the algorithm, highlighting the process of attaching completed nodes to the previous node and handling the completion of reverse post order traversal.', 'The chapter also mentions that the worst-case height is O(n) for the recursive solution, providing insights into the space complexity considerations.', 'The code for the iterative solution is provided, with an emphasis on understanding the intuition behind the iterative approach for clarity.']}], 'duration': 376.228, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR4258334.jpg', 'highlights': ['The algorithm involves storing the nodes whose reverse post order traversal is completed and then attaching the nodes to the previous node, resulting in a time complexity of O(n) and space complexity of O(n).', 'The iterative solution involves using a stack to store the nodes in a last in first out manner, extending the concept of recursion and demonstrating a time complexity of O(n) and space complexity of O(n).', 'The last node completed for post-order traversal will update its pointers to connect with the previous nodes, demonstrating the completion of the traversal process.', "The process involves updating pointers and assigning new values to 'previous' as the traversal progresses through the binary tree.", "The code explanation for traversing a binary tree involves initializing 'previous' as null, traversing the nodes, updating 'previous' and connecting 'right' and 'left' nodes with 'previous' and 'null'."]}, {'end': 940.461, 'segs': [{'end': 688.85, 'src': 'heatmap', 'start': 641.326, 'weight': 1, 'content': [{'end': 642.846, 'text': 'next, does car have a right?', 'start': 641.326, 'duration': 1.52}, {'end': 644.447, 'text': "yes, that's five.", 'start': 642.846, 'duration': 1.601}, {'end': 645.468, 'text': 'does car have a left?', 'start': 644.447, 'duration': 1.021}, {'end': 646.148, 'text': "yes, that's two.", 'start': 645.468, 'duration': 0.68}, {'end': 649.378, 'text': 'insert that right after that.', 'start': 647.597, 'duration': 1.781}, {'end': 651.779, 'text': 'right after that, curve is one right.', 'start': 649.378, 'duration': 2.401}, {'end': 656.481, 'text': "so over here what we'll do is we'll say once right should be st dot top.", 'start': 651.779, 'duration': 4.702}, {'end': 658.902, 'text': 'so once right should be two.', 'start': 656.481, 'duration': 2.421}, {'end': 664.004, 'text': "so i'm directly saying hey, one, your right should indeed be two.", 'start': 658.902, 'duration': 5.102}, {'end': 665.165, 'text': "that is what i'm saying.", 'start': 664.004, 'duration': 1.161}, {'end': 667.586, 'text': 'hey, one, your right should be indeed be two.', 'start': 665.165, 'duration': 2.421}, {'end': 673.725, 'text': "so what i'll do is i'll just use the yellow colors to mark the right bar, right links.", 'start': 667.586, 'duration': 6.139}, {'end': 677.586, 'text': "okay, after that i'm saying hey, your left is null.", 'start': 673.725, 'duration': 3.861}, {'end': 679.207, 'text': "so i'll use the red colors to mark null.", 'start': 677.586, 'duration': 1.621}, {'end': 680.747, 'text': 'so your left is null.', 'start': 679.207, 'duration': 1.54}, {'end': 685.549, 'text': "perfect, right after that i i've done this.", 'start': 680.747, 'duration': 4.802}, {'end': 688.85, 'text': 'so i come back again and curve will be like take two.', 'start': 685.549, 'duration': 3.301}], 'summary': 'Car navigation instructions: 5 right, 2 left, and 1 curve right. set right as 2 and mark null for left.', 'duration': 47.524, 'max_score': 641.326, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR4641326.jpg'}, {'end': 820.279, 'src': 'embed', 'start': 788.245, 'weight': 0, 'content': [{'end': 792.126, 'text': "5 says, I have a right, that's 6.", 'start': 788.245, 'duration': 3.881}, {'end': 792.846, 'text': "But I don't have a left.", 'start': 792.126, 'duration': 0.72}, {'end': 796.727, 'text': "Okay Next, 5's right points to 6.", 'start': 793.446, 'duration': 3.281}, {'end': 800.949, 'text': "Okay and five's left.", 'start': 796.727, 'duration': 4.222}, {'end': 803.59, 'text': "that's null.", 'start': 800.949, 'duration': 2.641}, {'end': 809.513, 'text': 'nice, next time you again come back and this time five will be changed to six.', 'start': 803.59, 'duration': 5.923}, {'end': 811.494, 'text': "six will say i don't have a right, but i have a left.", 'start': 809.513, 'duration': 1.981}, {'end': 812.435, 'text': "that's seven.", 'start': 811.494, 'duration': 0.941}, {'end': 820.279, 'text': 'and i put it this time six says my right will be seven and my left will be null.', 'start': 812.435, 'duration': 7.844}], 'summary': 'Progressing from 5 to 6, 6 to 7 with right and left pointers', 'duration': 32.034, 'max_score': 788.245, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR4788245.jpg'}, {'end': 864.895, 'src': 'embed', 'start': 840.415, 'weight': 3, 'content': [{'end': 847.437, 'text': "Once my iteration has ended, can I say like, if I just join the yellow dots, it's going to be one, two, like yellow.", 'start': 840.415, 'duration': 7.022}, {'end': 848.338, 'text': 'are the right dots right??', 'start': 847.437, 'duration': 0.901}, {'end': 853.159, 'text': 'Three, then a four, then a five, then a six and then a seven.', 'start': 848.378, 'duration': 4.781}, {'end': 860.048, 'text': "indeed, and that's that's how you can flatten a binary tree to a linked list very straightforward insert right,", 'start': 853.659, 'duration': 6.389}, {'end': 864.895, 'text': 'insert left and then just make sure you connect them right again.', 'start': 860.048, 'duration': 4.847}], 'summary': 'Flatten binary tree to linked list by joining yellow dots in sequence.', 'duration': 24.48, 'max_score': 840.415, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR4840415.jpg'}, {'end': 924.799, 'src': 'embed', 'start': 899.404, 'weight': 4, 'content': [{'end': 906.748, 'text': "that's why the intuition is of entering right first, then for left, so that whenever you have the right attached,", 'start': 899.404, 'duration': 7.344}, {'end': 909.449, 'text': "you'll automatically get it attached to the next cat.", 'start': 906.748, 'duration': 2.701}, {'end': 912.951, 'text': "that's that's a simple intuition behind inserting right first and then the left.", 'start': 909.449, 'duration': 3.502}, {'end': 918.118, 'text': 'Time complexity again stands out to be big of n.', 'start': 914.977, 'duration': 3.141}, {'end': 919.878, 'text': 'Space complexity, big of n.', 'start': 918.118, 'duration': 1.76}, {'end': 924.799, 'text': "So, we haven't significantly improved anything except ignoring recursion.", 'start': 919.878, 'duration': 4.921}], 'summary': 'Insert right before left to improve attachment, resulting in o(n) time and space complexity.', 'duration': 25.395, 'max_score': 899.404, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR4899404.jpg'}], 'start': 634.562, 'title': 'Linking right and left', 'summary': "Explains the process of linking right and left values in a coding scenario, involving the values 'five' and 'two', and establishing the right value as 'two' for 'one'. it also explains the process of flattening a binary tree to a linked list using a stack, with a time and space complexity of o(n), and emphasizes the intuitive approach of inserting right first, then left.", 'chapters': [{'end': 685.549, 'start': 634.562, 'title': 'Linking right and left', 'summary': "Explains the process of linking right and left values in a coding scenario, involving the values 'five' and 'two', and establishing the right value as 'two' for 'one'.", 'duration': 50.987, 'highlights': ["The process involves assigning the right value 'five' and left value 'two', then establishing the right value as 'two' for 'one'.", 'Using color codes to mark the right and left values, with yellow for right and red for null.', "The chapter emphasizes the direct assignment of the right value 'two' to 'one'."]}, {'end': 940.461, 'start': 685.549, 'title': 'Flatten binary tree to linked list', 'summary': 'Explains the process of flattening a binary tree to a linked list using a stack, with a time and space complexity of o(n), and emphasizes the intuitive approach of inserting right first, then left.', 'duration': 254.912, 'highlights': ['Process of flattening binary tree to linked list using stack The chapter details the step-by-step process of flattening a binary tree to a linked list using a stack and iterative approach.', 'Emphasizes intuitive approach of inserting right first, then left The approach of inserting right first and then left is highlighted as an intuitive method for connecting the nodes in the linked list.', 'Time complexity of O(n) and space complexity of O(n) The time complexity is O(n) and the space complexity is O(n) for the process of flattening the binary tree to a linked list.']}], 'duration': 305.899, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR4634562.jpg', 'highlights': ["The process involves assigning the right value 'five' and left value 'two', then establishing the right value as 'two' for 'one'.", 'Using color codes to mark the right and left values, with yellow for right and red for null.', "The chapter emphasizes the direct assignment of the right value 'two' to 'one'.", 'Process of flattening binary tree to linked list using stack The chapter details the step-by-step process of flattening a binary tree to a linked list using a stack and iterative approach.', 'Emphasizes intuitive approach of inserting right first, then left The approach of inserting right first and then left is highlighted as an intuitive method for connecting the nodes in the linked list.', 'Time complexity of O(n) and space complexity of O(n) The time complexity is O(n) and the space complexity is O(n) for the process of flattening the binary tree to a linked list.']}, {'end': 1302.356, 'segs': [{'end': 968.535, 'src': 'embed', 'start': 941.061, 'weight': 2, 'content': [{'end': 944.142, 'text': 'Okay, so let me explain what will be my thought process.', 'start': 941.061, 'duration': 3.081}, {'end': 954.93, 'text': "now can i say can i say uh, since this bani tree has to be converted into a linked list and essentially it's a pre-order, correct?", 'start': 944.907, 'duration': 10.023}, {'end': 958.792, 'text': 'so logically, this four should always connect to this five.', 'start': 954.93, 'duration': 3.862}, {'end': 960.952, 'text': "right, that's that's the logic.", 'start': 958.792, 'duration': 2.16}, {'end': 964.453, 'text': 'this four should always connect to the right.', 'start': 960.952, 'duration': 3.501}, {'end': 965.554, 'text': 'uh, the five.', 'start': 964.453, 'duration': 1.101}, {'end': 966.134, 'text': 'why? why?', 'start': 965.554, 'duration': 0.58}, {'end': 968.535, 'text': 'why does this four has to connect to five?', 'start': 966.134, 'duration': 2.401}], 'summary': 'Converting a binary tree to linked list involves pre-order logic, connecting 4 to 5.', 'duration': 27.474, 'max_score': 941.061, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR4941061.jpg'}, {'end': 1142.103, 'src': 'heatmap', 'start': 1044.579, 'weight': 0.713, 'content': [{'end': 1049.405, 'text': 'so initially i have a current which is a one which is standing at the root of the tree.', 'start': 1044.579, 'duration': 4.826}, {'end': 1051.867, 'text': 'so ideally i have to connect this four to five right.', 'start': 1049.405, 'duration': 2.462}, {'end': 1057.914, 'text': "so what i'll do is what i'll do is i will first see if car has a left, because if there is a left,", 'start': 1051.867, 'duration': 6.047}, {'end': 1062.416, 'text': 'then only it will get connected between 1 and 5 frames if there is a left only.', 'start': 1058.434, 'duration': 3.982}, {'end': 1066.919, 'text': "so if it is having null and i'm not having null, then i'll take a previous.", 'start': 1062.416, 'duration': 4.503}, {'end': 1070.48, 'text': "okay. so let's take a previous which is saying i'm two, okay.", 'start': 1066.919, 'duration': 3.561}, {'end': 1072.101, 'text': "so i've taken a previous which is two.", 'start': 1070.48, 'duration': 1.621}, {'end': 1074.703, 'text': "what i'm saying is go on till previous.", 'start': 1072.101, 'duration': 2.602}, {'end': 1075.764, 'text': 'right is not null.', 'start': 1074.703, 'duration': 1.061}, {'end': 1081.13, 'text': 'so previous will say okay, i can go on four, but i cannot go beyond four because force right is null.', 'start': 1075.764, 'duration': 5.366}, {'end': 1082.912, 'text': "so i'll go till four, perfect.", 'start': 1081.13, 'duration': 1.782}, {'end': 1084.693, 'text': "now i'm saying force right.", 'start': 1082.912, 'duration': 1.781}, {'end': 1086.395, 'text': "why don't you go to curse right?", 'start': 1084.693, 'duration': 1.702}, {'end': 1088.837, 'text': 'cur is one force right.', 'start': 1086.395, 'duration': 2.442}, {'end': 1089.718, 'text': "that's this.", 'start': 1088.837, 'duration': 0.881}, {'end': 1092.541, 'text': "why don't you go to curse right, perfect.", 'start': 1089.718, 'duration': 2.823}, {'end': 1095.384, 'text': "next i'm saying curse right should be curse left.", 'start': 1092.541, 'duration': 2.843}, {'end': 1101.622, 'text': "so i'm saying this guy, so one's right is pointing to two, and i've made sure that this happens.", 'start': 1095.384, 'duration': 6.238}, {'end': 1105.146, 'text': 'the next thing that i just need to do is i have to make sure three comes in between them.', 'start': 1101.622, 'duration': 3.524}, {'end': 1107.127, 'text': "so i've done the first thing perfect.", 'start': 1105.146, 'duration': 1.981}, {'end': 1110.41, 'text': "next i'm saying cur, why don't you move to cur right?", 'start': 1107.127, 'duration': 3.283}, {'end': 1112.592, 'text': "so cur's right is two.", 'start': 1110.41, 'duration': 2.182}, {'end': 1115.034, 'text': 'so i moved it, perfect.', 'start': 1112.592, 'duration': 2.442}, {'end': 1116.236, 'text': "next let's come back again.", 'start': 1115.034, 'duration': 1.202}, {'end': 1118.938, 'text': 'does uh, two have a left?', 'start': 1116.236, 'duration': 2.702}, {'end': 1119.999, 'text': 'indeed it has.', 'start': 1118.938, 'duration': 1.061}, {'end': 1123.911, 'text': 'so previous will be this time 3..', 'start': 1119.999, 'duration': 3.912}, {'end': 1126.352, 'text': "And I'll go on to right if there is any.", 'start': 1123.911, 'duration': 2.441}, {'end': 1128.374, 'text': "So that doesn't exist any right.", 'start': 1126.713, 'duration': 1.661}, {'end': 1130.435, 'text': 'So this while loop will not be executed.', 'start': 1128.774, 'duration': 1.661}, {'end': 1131.816, 'text': "I'm saying previous right.", 'start': 1130.855, 'duration': 0.961}, {'end': 1133.737, 'text': 'Previous is 3.', 'start': 1132.417, 'duration': 1.32}, {'end': 1134.278, 'text': "It's right.", 'start': 1133.737, 'duration': 0.541}, {'end': 1137.12, 'text': "Should point to Kerr's right.", 'start': 1134.918, 'duration': 2.202}, {'end': 1138.921, 'text': "So it's point to here.", 'start': 1138.08, 'duration': 0.841}, {'end': 1140.262, 'text': 'Again Super simple.', 'start': 1139.221, 'duration': 1.041}, {'end': 1142.103, 'text': "And I'm saying Kerr's right.", 'start': 1141.142, 'duration': 0.961}], 'summary': 'Traversing a tree structure to connect nodes; 1, 2, 3, 4, and 5.', 'duration': 97.524, 'max_score': 1044.579, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR41044579.jpg'}, {'end': 1280.321, 'src': 'embed', 'start': 1239.393, 'weight': 0, 'content': [{'end': 1247.179, 'text': 'On the left subtree, whichever is the last guy which will be performed on pre-order, I just took that and connected to the right of the current node.', 'start': 1239.393, 'duration': 7.786}, {'end': 1249.861, 'text': 'That is what the simple intuition is.', 'start': 1247.52, 'duration': 2.341}, {'end': 1258.829, 'text': 'I repeat, on the left subtree, whichever is the last node of pre-order, I connected it to the right of the node, right of the root.', 'start': 1250.242, 'duration': 8.587}, {'end': 1260.51, 'text': "that's it.", 'start': 1259.309, 'duration': 1.201}, {'end': 1262.211, 'text': 'that is what i needed to do,', 'start': 1260.51, 'duration': 1.701}, {'end': 1271.755, 'text': 'and i just kept on doing that for every tree and ultimately i could easily traverse and change the pointers in big of n time and big of one space.', 'start': 1262.211, 'duration': 9.544}, {'end': 1272.916, 'text': "that's very important.", 'start': 1271.755, 'duration': 1.161}, {'end': 1274.657, 'text': 'big of one space is what i took.', 'start': 1272.916, 'duration': 1.741}, {'end': 1277.259, 'text': 'So that is how we will do this.', 'start': 1275.157, 'duration': 2.102}, {'end': 1280.321, 'text': 'So, I hope you have understood the entire explanation as well as the code.', 'start': 1277.919, 'duration': 2.402}], 'summary': 'Connected last node of left subtree to right of root, achieving o(n) time and o(1) space.', 'duration': 40.928, 'max_score': 1239.393, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR41239393.jpg'}], 'start': 941.061, 'title': 'Converting bani tree to linked list and connecting frames in tree', 'summary': 'Explains converting a bani tree into a linked list using pre-order traversal, emphasizing nodes four and five. it also covers connecting frames in a tree to achieve o(n) time complexity and o(1) space complexity.', 'chapters': [{'end': 1057.914, 'start': 941.061, 'title': 'Converting bani tree to linked list', 'summary': 'Explains the process of converting a bani tree into a linked list using pre-order traversal and discusses the logical connection between nodes, with particular emphasis on the connection between nodes four and five. the chapter also delves into the code implementation of this process.', 'duration': 116.853, 'highlights': ['The logical connection between nodes four and five is discussed, emphasizing the necessity for node four to connect to node five due to the pre-order nature of the tree traversal.', 'The process of connecting the last node of the left subtree to the right of a specific node is explained as a key step in the conversion process.', 'The code implementation for connecting nodes and traversing the Bani tree is outlined, with a focus on the initial setup and the process of connecting nodes four and five.']}, {'end': 1302.356, 'start': 1058.434, 'title': 'Connecting frames in tree', 'summary': 'Explains the process of connecting frames in a tree, using a simple intuition to connect the last node of the left subtree to the right of the root, achieving a time complexity of o(n) and space complexity of o(1).', 'duration': 243.922, 'highlights': ['The process involves connecting the last node of the left subtree to the right of the root, achieved in O(n) time and O(1) space.', 'The approach ensures traversal and changing of pointers for every tree, enabling efficient execution.', 'The explanation emphasizes the use of a simple intuition to connect frames, resulting in a time complexity of O(n) and space complexity of O(1).']}], 'duration': 361.295, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/sWf7k1x9XR4/pics/sWf7k1x9XR4941061.jpg', 'highlights': ['The process involves connecting the last node of the left subtree to the right of the root, achieved in O(n) time and O(1) space.', 'The explanation emphasizes the use of a simple intuition to connect frames, resulting in a time complexity of O(n) and space complexity of O(1).', 'The logical connection between nodes four and five is discussed, emphasizing the necessity for node four to connect to node five due to the pre-order nature of the tree traversal.', 'The process of connecting the last node of the left subtree to the right of a specific node is explained as a key step in the conversion process.', 'The code implementation for connecting nodes and traversing the Bani tree is outlined, with a focus on the initial setup and the process of connecting nodes four and five.']}], 'highlights': ['Releval by Unacademy is a hiring platform for freshers and experienced individuals in top Indian companies.', 'Companies like CRED, UpGrad, Urban Company, Razorpay are accessible through Releval by Unacademy.', 'Candidates are hired based solely on their skills and performance in the relevant test.', 'The process of flattening a binary tree into a linked list is explained, emphasizing the rearrangement of nodes to represent the pre-order of the binary tree as the linked list.', 'Implementing a reverse post order traversal to rearrange and attach nodes in a tree can improve the efficiency of the algorithm. By using a reverse post order traversal, the algorithm aims to achieve a specific sequence of node arrangements, potentially improving efficiency.', 'The algorithm involves storing the nodes whose reverse post order traversal is completed and then attaching the nodes to the previous node, resulting in a time complexity of O(n) and space complexity of O(n).', 'The iterative solution involves using a stack to store the nodes in a last in first out manner, extending the concept of recursion and demonstrating a time complexity of O(n) and space complexity of O(n).', "The process involves updating pointers and assigning new values to 'previous' as the traversal progresses through the binary tree.", "The process involves assigning the right value 'five' and left value 'two', then establishing the right value as 'two' for 'one'.", 'Using color codes to mark the right and left values, with yellow for right and red for null.', "The chapter emphasizes the direct assignment of the right value 'two' to 'one'.", 'Process of flattening binary tree to linked list using stack The chapter details the step-by-step process of flattening a binary tree to a linked list using a stack and iterative approach.', 'Emphasizes intuitive approach of inserting right first, then left The approach of inserting right first and then left is highlighted as an intuitive method for connecting the nodes in the linked list.', 'The process involves connecting the last node of the left subtree to the right of the root, achieved in O(n) time and O(1) space.', 'The explanation emphasizes the use of a simple intuition to connect frames, resulting in a time complexity of O(n) and space complexity of O(1).']}