title

L29. Children Sum Property in Binary Tree | O(N) Approach | 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': 'L29. Children Sum Property in Binary Tree | O(N) Approach | C++ | Java', 'heatmap': [{'end': 906.718, 'start': 844.238, 'weight': 0.706}], 'summary': 'Relevel, sponsored by unacademy, offers job opportunities in front-end, back-end, and business development for freshers and early career individuals, with mentoring sessions and a quick hiring process. the chapter discusses maintaining children sum property in a binary tree, ensuring node values equal the sum of their children, with examples, complexity, and a linear solution of o(n) time complexity. it also explains a traversal method to convert a binary tree to satisfy the children sum property, providing c++ and java solutions with o(n) time complexity.', 'chapters': [{'end': 33.377, 'segs': [{'end': 33.377, 'src': 'embed', 'start': 0.029, 'weight': 0, 'content': [{'end': 4.112, 'text': "So before starting this video, I'd love to thank Relevel for sponsoring this entire video.", 'start': 0.029, 'duration': 4.083}, {'end': 9.016, 'text': 'A hiring platform with no degree required, no experience required, mentoring sessions available.', 'start': 4.532, 'duration': 4.484}, {'end': 15.6, 'text': "Feels like a dream, isn't it? What if I say all of this is for free? Well, Relevel by Unacademy is here to make your dream come true.", 'start': 9.276, 'duration': 6.324}, {'end': 21.785, 'text': "With job opportunities in front-end, back-end and business development from India's top companies for freshers and people in the early career.", 'start': 15.74, 'duration': 6.045}, {'end': 26.71, 'text': 'reliable, is here to make the entire hiring process super simple and super quick.', 'start': 22.165, 'duration': 4.545}, {'end': 32.316, 'text': 'all you have to do is to give the relevant test and, based on your score, interviews will be scheduled and you will be hired.', 'start': 26.71, 'duration': 5.606}, {'end': 33.377, 'text': 'so what are you waiting for?', 'start': 32.316, 'duration': 1.061}], 'summary': "Relevel by unacademy offers free mentoring and job opportunities in front-end, back-end, and business development from india's top companies for freshers and early-career individuals.", 'duration': 33.348, 'max_score': 0.029, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fnmisPM6cVo/pics/fnmisPM6cVo29.jpg'}], 'start': 0.029, 'title': 'Relevel by unacademy', 'summary': "Highlights relevel, a hiring platform sponsored by unacademy, offering job opportunities in front-end, back-end, and business development from india's top companies for freshers and early career individuals, with mentoring sessions and a simple, quick hiring process based on relevant tests.", 'chapters': [{'end': 33.377, 'start': 0.029, 'title': 'Relevel by unacademy: job opportunities for freshers', 'summary': "Highlights relevel, a hiring platform sponsored by unacademy, offering job opportunities in front-end, back-end, and business development from india's top companies for freshers and individuals in early career, with mentoring sessions and a simple, quick hiring process based on relevant tests.", 'duration': 33.348, 'highlights': ["Relevel by Unacademy offers job opportunities in front-end, back-end, and business development from India's top companies for freshers and individuals in the early career with no degree or experience required.", 'The platform provides mentoring sessions and a simple, quick hiring process based on relevant tests and interview scheduling, making the dream job accessible to all.', 'Sponsored by Relevel, the hiring process is free, making it accessible to everyone and eliminating financial barriers to job opportunities.']}], 'duration': 33.348, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fnmisPM6cVo/pics/fnmisPM6cVo29.jpg', 'highlights': ["Relevel by Unacademy offers job opportunities in front-end, back-end, and business development from India's top companies for freshers and individuals in the early career with no degree or experience required.", 'The platform provides mentoring sessions and a simple, quick hiring process based on relevant tests and interview scheduling, making the dream job accessible to all.', 'Sponsored by Relevel, the hiring process is free, making it accessible to everyone and eliminating financial barriers to job opportunities.']}, {'end': 347.568, 'segs': [{'end': 91.832, 'src': 'embed', 'start': 56.038, 'weight': 1, 'content': [{'end': 58.6, 'text': 'it can be complete, it can be full, it can be like.', 'start': 56.038, 'duration': 2.562}, {'end': 66.487, 'text': 'it can be any shape binary tree and like in this binary tree, you have to maintain the children sum property.', 'start': 58.6, 'duration': 7.887}, {'end': 68.409, 'text': 'now, what is this property?', 'start': 66.487, 'duration': 1.922}, {'end': 71.752, 'text': 'it basically states that for any node,', 'start': 68.409, 'duration': 3.343}, {'end': 82.041, 'text': 'the value should be like the value at the node should be equivalent to its left nodes value plus the right nodes value.', 'start': 71.752, 'duration': 10.289}, {'end': 91.832, 'text': 'and if the if the binary tree does not follows the children sum property, what you can do is you can basically increment.', 'start': 82.845, 'duration': 8.987}], 'summary': 'Maintain children sum property in a binary tree.', 'duration': 35.794, 'max_score': 56.038, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fnmisPM6cVo/pics/fnmisPM6cVo56038.jpg'}, {'end': 138.595, 'src': 'embed', 'start': 107.663, 'weight': 2, 'content': [{'end': 110.786, 'text': 'okay, so assume this is the binary tree that is given to you.', 'start': 107.663, 'duration': 3.123}, {'end': 116.752, 'text': 'So, in order to maintain the children sum property, this node is having a value 2..', 'start': 111.306, 'duration': 5.446}, {'end': 122.619, 'text': 'So this 2 is not equivalent to 35 plus 10.', 'start': 116.752, 'duration': 5.867}, {'end': 123.66, 'text': "It's not equivalent.", 'start': 122.619, 'duration': 1.041}, {'end': 127.364, 'text': 'So what you will do is you will basically increment 2.', 'start': 124.001, 'duration': 3.363}, {'end': 131.388, 'text': 'yes, this node value you will increment to something as 45.', 'start': 127.364, 'duration': 4.024}, {'end': 138.595, 'text': "okay. so if you increment this 2 to 45, you'll get 35 plus 10 to 45.", 'start': 131.388, 'duration': 7.207}], 'summary': 'To maintain children sum property, increment node value from 2 to 45 for equivalence to 35 + 10.', 'duration': 30.932, 'max_score': 107.663, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fnmisPM6cVo/pics/fnmisPM6cVo107663.jpg'}, {'end': 210.873, 'src': 'embed', 'start': 159.475, 'weight': 0, 'content': [{'end': 163.799, 'text': 'It completely depends on you how you want to increment the node.', 'start': 159.475, 'duration': 4.324}, {'end': 170.665, 'text': 'Just make sure whenever you are incrementing the node, the node value should be equivalent to the left child value.', 'start': 164.219, 'duration': 6.446}, {'end': 172.888, 'text': 'value plus right child value.', 'start': 171.127, 'duration': 1.761}, {'end': 174.808, 'text': "that's the main criteria.", 'start': 172.888, 'duration': 1.92}, {'end': 180.17, 'text': "so what i've done is i've incremented this node, i've incremented this node and i've incremented this node.", 'start': 174.808, 'duration': 5.362}, {'end': 184.131, 'text': "so once i've incremented this now you can see it follows 45 is a summation of 35 plus 10.", 'start': 180.17, 'duration': 3.961}, {'end': 193.115, 'text': '35 is a summation of 30 plus 5.', 'start': 184.131, 'duration': 8.984}, {'end': 195.617, 'text': '10 is a summation of 8 plus 2.', 'start': 193.115, 'duration': 2.502}, {'end': 201.541, 'text': 'so this binary tree, after modification, is following the children sum property.', 'start': 195.617, 'duration': 5.924}, {'end': 204.243, 'text': 'now you might be thinking what is the big deal in this?', 'start': 201.541, 'duration': 2.702}, {'end': 210.873, 'text': 'take this 35, take this 10, add them up and if This is to just increase it to whatever is the addition.', 'start': 204.243, 'duration': 6.63}], 'summary': 'Increment binary tree nodes to satisfy children sum property.', 'duration': 51.398, 'max_score': 159.475, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fnmisPM6cVo/pics/fnmisPM6cVo159475.jpg'}, {'end': 337.958, 'src': 'embed', 'start': 302.962, 'weight': 4, 'content': [{'end': 304.463, 'text': "So there's no guarantee to that.", 'start': 302.962, 'duration': 1.501}, {'end': 310.867, 'text': 'Also, there is no guarantee that if you have 50 and it is like 7 and 2, you increase this value.', 'start': 305.003, 'duration': 5.864}, {'end': 315.67, 'text': 'then also there is no guarantee that these guys will help you out right.', 'start': 311.909, 'duration': 3.761}, {'end': 319.432, 'text': "so it's not a simple problem as it looks like.", 'start': 315.67, 'duration': 3.762}, {'end': 324.474, 'text': 'the problem is kind of you have to convert the binary tree into a binary tree which follows the children sum property.', 'start': 319.432, 'duration': 5.042}, {'end': 331.296, 'text': "so if you look out the solution that's given at gfg, that's a solution which follows the bigo of n square.", 'start': 324.474, 'duration': 6.822}, {'end': 337.958, 'text': "also, if you read a lot of articles, you'll find that the solution that every article proposes is big of n square.", 'start': 331.296, 'duration': 6.662}], 'summary': 'The problem involves converting a binary tree to follow the children sum property, with solutions typically having a time complexity of o(n^2).', 'duration': 34.996, 'max_score': 302.962, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fnmisPM6cVo/pics/fnmisPM6cVo302962.jpg'}], 'start': 33.377, 'title': 'Maintaining children sum property in binary tree', 'summary': 'Discusses maintaining children sum property in a binary tree by incrementing node values to ensure they equal the sum of their children, with examples. it also explains the concept, complexity, and a linear solution with o(n) time complexity.', 'chapters': [{'end': 180.17, 'start': 33.377, 'title': 'Maintaining children sum property in binary tree', 'summary': 'Explains how to maintain the children sum property in a binary tree by incrementing node values to ensure they are equivalent to the sum of their left and right child values, with examples provided.', 'duration': 146.793, 'highlights': ["The chapter explains the concept of maintaining the children sum property in a binary tree. It discusses the requirement to ensure that the value at any node should be equivalent to the sum of its left and right nodes' values.", 'The example demonstrates the process of incrementing node values to maintain the children sum property in a given binary tree. It provides an example of incrementing node values to satisfy the property, with specific values and calculations mentioned.', 'The chapter emphasizes the freedom to choose the increment values for nodes, as long as the property is maintained. It highlights the flexibility in choosing the increment values for nodes while ensuring that the node value remains equivalent to the sum of its left and right child values.']}, {'end': 347.568, 'start': 180.17, 'title': 'Binary tree children sum property', 'summary': "Discusses the concept of children sum property in a binary tree and explains the complexity of converting a binary tree to follow this property, providing a solution that is linear in nature and can be done by a single traversal with a time complexity of o(n). key points include the explanation of the children sum property, the complexity of the problem, and the proposed solution's efficiency.", 'duration': 167.398, 'highlights': ["The problem of converting a binary tree to follow the children sum property is complex as it involves ensuring that the parent node's value is equal to the sum of its children's values, with the constraint that the value can only be increased by 1 and not decreased. Complexity of the problem, constraint on increasing the value, explanation of children sum property", 'The proposed solution for converting a binary tree to follow the children sum property is linear in nature and can be achieved with a single traversal, providing an efficient time complexity of O(n). Efficiency of the solution, linear in nature, time complexity of O(n)', 'Existing solutions for the problem typically have a time complexity of O(n^2), making them less efficient compared to the linear solution being presented. Comparison of efficiency, time complexity']}], 'duration': 314.191, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fnmisPM6cVo/pics/fnmisPM6cVo33377.jpg', 'highlights': ['The proposed solution for converting a binary tree to follow the children sum property is linear in nature and can be achieved with a single traversal, providing an efficient time complexity of O(n).', "The chapter explains the concept of maintaining the children sum property in a binary tree. It discusses the requirement to ensure that the value at any node should be equivalent to the sum of its left and right nodes' values.", 'The example demonstrates the process of incrementing node values to maintain the children sum property in a given binary tree. It provides an example of incrementing node values to satisfy the property, with specific values and calculations mentioned.', 'The chapter emphasizes the freedom to choose the increment values for nodes, as long as the property is maintained. It highlights the flexibility in choosing the increment values for nodes while ensuring that the node value remains equivalent to the sum of its left and right child values.', "The problem of converting a binary tree to follow the children sum property is complex as it involves ensuring that the parent node's value is equal to the sum of its children's values, with the constraint that the value can only be increased by 1 and not decreased."]}, {'end': 964.314, 'segs': [{'end': 406.215, 'src': 'embed', 'start': 371.921, 'weight': 2, 'content': [{'end': 372.822, 'text': 'The question is not that.', 'start': 371.921, 'duration': 0.901}, {'end': 375.284, 'text': 'Question is convert a binary tree to.', 'start': 373.222, 'duration': 2.062}, {'end': 383.712, 'text': 'any binary tree that actually follows the childrensome property by increasing the node by a value plus one as many times as you want?', 'start': 376.045, 'duration': 7.667}, {'end': 384.974, 'text': 'that is the question.', 'start': 383.712, 'duration': 1.262}, {'end': 386.955, 'text': "so, guys, let's see the solution.", 'start': 384.974, 'duration': 1.981}, {'end': 392.781, 'text': "so, in order to solve this problem, i'll be smart and i'll be using the recursive traversal okay,", 'start': 386.955, 'duration': 5.826}, {'end': 399.888, 'text': 'where i move left and then i move right and then i come back from left and then i come back from right.', 'start': 393.12, 'duration': 6.768}, {'end': 406.215, 'text': "so that's what i am going to use this kind of traversal where i go left, go right and then i come back.", 'start': 399.888, 'duration': 6.327}], 'summary': 'Convert a binary tree to follow childrensome property by increasing nodes by a value plus one using recursive traversal.', 'duration': 34.294, 'max_score': 371.921, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fnmisPM6cVo/pics/fnmisPM6cVo371921.jpg'}, {'end': 769.697, 'src': 'embed', 'start': 737.818, 'weight': 1, 'content': [{'end': 743.584, 'text': 'This 100 plus this 100 will give you 200.', 'start': 737.818, 'duration': 5.766}, {'end': 749.106, 'text': 'So yeah, this does not guarantee you that the transition will be with smaller values,', 'start': 743.584, 'duration': 5.522}, {'end': 757.27, 'text': 'but it does guarantee you that any given binary tree can be converted to a binary tree which follows the children sum property.', 'start': 749.106, 'duration': 8.164}, {'end': 761.692, 'text': 'And I have done this in one simple traversal.', 'start': 757.85, 'duration': 3.842}, {'end': 769.697, 'text': 'so if you did not understand the intuition, i will highly recommend that you go back and repeat this again and even after that,', 'start': 762.432, 'duration': 7.265}], 'summary': 'Binary tree can be converted to follow children sum property, using one simple traversal.', 'duration': 31.879, 'max_score': 737.818, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fnmisPM6cVo/pics/fnmisPM6cVo737818.jpg'}, {'end': 806.148, 'src': 'embed', 'start': 779.825, 'weight': 0, 'content': [{'end': 785.309, 'text': 'you will see that it actually makes sense to increase the values as we go down and while coming back,', 'start': 779.825, 'duration': 5.484}, {'end': 790.494, 'text': 'we just sum it up so that we never feel short of numbers.', 'start': 785.309, 'duration': 5.185}, {'end': 793.617, 'text': "so let's discuss the c plus plus as well as the java solution.", 'start': 790.494, 'duration': 3.123}, {'end': 795.198, 'text': 'c plus plus code is on the left.', 'start': 793.617, 'duration': 1.581}, {'end': 799.802, 'text': "the java code is on the right, so you're given a root of the binary tree.", 'start': 795.198, 'duration': 4.604}, {'end': 802.745, 'text': 'so what i do is i i do a left, right traversal.', 'start': 799.802, 'duration': 2.943}, {'end': 806.148, 'text': "so initially i check if the root is null, i'll return all else.", 'start': 802.745, 'duration': 3.403}], 'summary': 'Increase values as we descend, sum up when returning. discuss c++ and java solutions for binary tree traversal.', 'duration': 26.323, 'max_score': 779.825, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fnmisPM6cVo/pics/fnmisPM6cVo779825.jpg'}, {'end': 906.718, 'src': 'heatmap', 'start': 844.238, 'weight': 0.706, 'content': [{'end': 849.662, 'text': "so I'll go to this else and I'll say hey 50, why don't you assign yourself to the left?", 'start': 844.238, 'duration': 5.424}, {'end': 850.983, 'text': 'that is what is done here.', 'start': 849.662, 'duration': 1.321}, {'end': 853.485, 'text': "hey 50, why don't you assign yourself to the right?", 'start': 850.983, 'duration': 2.502}, {'end': 854.066, 'text': 'that is done here.', 'start': 853.485, 'duration': 0.581}, {'end': 863.008, 'text': 'so if it is lesser, if it is lesser, i assign, and if it is not lesser, and if the left plus right is greater, i increase the roots value.', 'start': 854.466, 'duration': 8.542}, {'end': 867.409, 'text': 'yes, i increase the roots value so that we do not feel short of anything.', 'start': 863.008, 'duration': 4.401}, {'end': 875.591, 'text': 'after that, i move to the left, i move to the right and when i come back, yes, i move, and when i come, i move, and when i come.', 'start': 867.409, 'duration': 8.182}, {'end': 879.213, 'text': 'so when i come back, i simply sum up left and right.', 'start': 875.591, 'duration': 3.622}, {'end': 886.882, 'text': 'i sum up left and right, and what i do is i assign that to the root, like whatever is on the left, whatever is on the right.', 'start': 879.213, 'duration': 7.669}, {'end': 888.904, 'text': "assume it's a hundred, it's a hundred.", 'start': 886.882, 'duration': 2.022}, {'end': 896.391, 'text': 'so i take hundred, i take hundred and i add it to get 200 and there is a check like it should not be leaf node.', 'start': 888.904, 'duration': 7.487}, {'end': 898.572, 'text': "in case of a leaf node, you don't update it.", 'start': 896.391, 'duration': 2.181}, {'end': 901.714, 'text': 'if it is not a leaf node, then only you update.', 'start': 898.572, 'duration': 3.142}, {'end': 903.015, 'text': 'the upper gap.', 'start': 901.714, 'duration': 1.301}, {'end': 906.718, 'text': 'like this is when you move up right, and this is when you move down.', 'start': 903.015, 'duration': 3.703}], 'summary': 'Algorithm updates nodes based on left and right values, increasing root value to prevent shortage.', 'duration': 62.48, 'max_score': 844.238, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fnmisPM6cVo/pics/fnmisPM6cVo844238.jpg'}], 'start': 347.568, 'title': 'Binary tree traversal and conversion', 'summary': "Explains a traversal method to convert a binary tree to satisfy the children sum property, ensuring that the sum of values of a node's children are greater than or equal to the node's value, and provides c++ and java solutions with a time complexity of o(n).", 'chapters': [{'end': 392.781, 'start': 347.568, 'title': "Converting binary tree to follow children's property", 'summary': "Discusses converting a binary tree to follow the children's property by increasing the node by a value plus one as many times as needed, emphasizing the use of recursive traversal for the solution.", 'duration': 45.213, 'highlights': ["The chapter discusses converting a binary tree to follow the children's property by increasing the node by a value plus one as many times as needed.", 'Emphasizes the use of recursive traversal for the solution.']}, {'end': 964.314, 'start': 393.12, 'title': 'Binary tree traversal and conversion', 'summary': "Explains a traversal method to convert a binary tree to satisfy the children sum property, ensuring that the sum of values of a node's children are greater than or equal to the node's value, and provides c++ and java solutions with a time complexity of o(n).", 'duration': 571.194, 'highlights': ['The traversal method involves moving left and right, and updating node values to ensure they satisfy the children sum property, with an explanation of the algorithm and its guarantee of converting any given binary tree to satisfy the property.', "The provided C++ and Java solutions utilize a recursive traversal approach with a time complexity of O(n) and space complexity of O(height of the tree), with an explanation of the code's logic and efficiency."]}], 'duration': 616.746, 'thumbnail': 'https://coursnap.oss-ap-southeast-1.aliyuncs.com/video-capture/fnmisPM6cVo/pics/fnmisPM6cVo347568.jpg', 'highlights': ['The provided C++ and Java solutions utilize a recursive traversal approach with a time complexity of O(n) and space complexity of O(height of the tree).', 'The traversal method involves moving left and right, and updating node values to ensure they satisfy the children sum property, with an explanation of the algorithm and its guarantee of converting any given binary tree to satisfy the property.', "The chapter discusses converting a binary tree to follow the children's property by increasing the node by a value plus one as many times as needed.", 'Emphasizes the use of recursive traversal for the solution.']}], 'highlights': ["Relevel by Unacademy offers job opportunities in front-end, back-end, and business development from India's top companies for freshers and individuals in the early career with no degree or experience required.", 'The platform provides mentoring sessions and a simple, quick hiring process based on relevant tests and interview scheduling, making the dream job accessible to all.', 'Sponsored by Relevel, the hiring process is free, making it accessible to everyone and eliminating financial barriers to job opportunities.', 'The proposed solution for converting a binary tree to follow the children sum property is linear in nature and can be achieved with a single traversal, providing an efficient time complexity of O(n).', 'The provided C++ and Java solutions utilize a recursive traversal approach with a time complexity of O(n) and space complexity of O(height of the tree).', "The chapter explains the concept of maintaining the children sum property in a binary tree. It discusses the requirement to ensure that the value at any node should be equivalent to the sum of its left and right nodes' values.", 'The example demonstrates the process of incrementing node values to maintain the children sum property in a given binary tree. It provides an example of incrementing node values to satisfy the property, with specific values and calculations mentioned.', 'The chapter emphasizes the freedom to choose the increment values for nodes, as long as the property is maintained. It highlights the flexibility in choosing the increment values for nodes while ensuring that the node value remains equivalent to the sum of its left and right child values.', "The problem of converting a binary tree to follow the children sum property is complex as it involves ensuring that the parent node's value is equal to the sum of its children's values, with the constraint that the value can only be increased by 1 and not decreased.", 'The traversal method involves moving left and right, and updating node values to ensure they satisfy the children sum property, with an explanation of the algorithm and its guarantee of converting any given binary tree to satisfy the property.', "The chapter discusses converting a binary tree to follow the children's property by increasing the node by a value plus one as many times as needed.", 'Emphasizes the use of recursive traversal for the solution.']}