Kth Largest Sum in a Binary Tree - Leetcode 2583 - Python

NeetCodeIO · Intermediate ·⚡ Algorithms & Data Structures ·1y ago

Key Takeaways

The video demonstrates how to solve the Kth Largest Sum in a Binary Tree problem using BFS and heaps, with a focus on time complexity analysis and efficient algorithms.

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve a problem K largest sum in a binary tree conceptually pretty simple problem suppose we're given a binary tree that looks like this what we want to do is compute the level sum of each level in the tree so that's relatively simple can you guess which algorithm we're going to use to do that I mean we could use either DFS or BFS those are kind of the main algorithms that we use on trees technically either will work to compute these but I'm going to prefer the BFS approach it's kind of a more natural way to do this so knowing that what do we want to do with those level sums assume we had them we have five here we have 17 here 13 here and we have 10 here well among all of these we want to find the K largest element among these elements so we pretty much removed the part that we needed a tree for now that we have these integers we don't really need to worry about the tree anymore now it's just a matter of finding the K largest element from this set of elements the obvious way to do it is to sort this input so what's the time complexity of that going to be before you think that it's n well let's assume that n is actually the number of nodes in this tree so then you might say well how many levels are going to be in the tree well if it's a balanced tree the height of the tree is going to be log n so the size of this is going to be log n but I'm not going to focus on that case I'm going to consider the worst case where the height of the tree is actually equal to n that would be the case where it's pretty much like a linked list like something like this so I'm going to to be more precise use H for the height of the tree so let's say the length of this is going to be of length H which in the worst case could be equal to n the time complexity to sort that is going to be H log H and of course we're going to have to go through everything in the input so the time complex is going to be n where n is the number of nodes plus h log H that's like the overall time complexity and once we have like sorted input we just return I think the length of like this list minus a k because we want the K largest so that's a perfectly valid way to solve this problem but we can actually do a little bit better let me show you how if we instead of sorting we take this and heapify it we turn it into a heap which if this is of size a we can do that in Big O of H so far the time complexity will be n from traversing the tree plus h from turning this into a heap and then what kind of Heap would we want to make it if we want to return the K largest element let's turn it into a Max heap if we do that we'll only have to pop from that Heap up to K times so we can say k time log H so in the event that K is relatively small this this will be not too bad now one thing I probably should have mentioned earlier is the fact that we might not actually have K levels in the tree for example in this tree like this is Level 1 2 3 4 if we have K = 5 well then we don't have a fifth level and in that case we return a default value of negative 1 so that's pretty easy to handle which is why I wasn't really too focused on that so this Max Heap approach is valid but there is one more approach we can take it's a little bit clever it involves using a Min Heap and I'm going to leave this here this is the max Heap time complexity and we're going to compare it to the Min Heap solution so the Min Heap solution is going to be kind of clever the idea is that we're going to maintain a minimum heap of size K it's always going to be less than or equal to K and the reason we're making it a Min Heap is because every time we push an element like as we're going through this level by level we're going to push this to the Heap we're going to push this to the Heap and let's say k is two in this example we're going to push that to the Heap as well and then since we want the Heap to only be up to size two we are going to remove the minimum element from the Heap so in other words the Min Heap is always going to store the K largest numbers the K largest levels and so if we do it this way once again we're going to get to this level and we're going to see okay now our Heap popped the minimum this is the minimum so this is what our Heap is going to look like at the end and then at the end we want the K largest element if these are the K largest elements we want the minimum among all of those elements that's why we use the men Heap we can get the men element in constant time so in this example that will be 13 so what's the time complexity of this solution well once again we are going to Traverse the tree so it's going to be n plus the size of the Heap is always going to be up to size K so pushing and popping from the Heap is going to be of size K we're going to do that roughly H times one for each level so the overall time complexity of this approach is going to be n + H * log K now let's consider the case where the tree is not balanced well then the H here would turn into an N so this would be n log K and over here this would be K log n so if the tree is not balanced K could also be pretty big like K could be approximately equal to n so I guess like in the worst case both of these time complexities would be roughly similar what about the case where the trees are balanced well in that case h would be approximately log n in which case this time complexity would turn into log n * log K plus that n term and then this time complexity would turn into K * log of log n and I guess like the upper bound of K itself is also equal to log in roughly if like it's a balance tree so I mean at this point I guess we're just kind of confusing ourselves either way I think both of these Solutions are pretty efficient I don't think in a real interview you would be asked to kind of explain why one is slightly more optimal than the other so I'll just leave things here but I thought like this kind of stuff was worth discussing thinking about the worst case and the best case run times I will be coding up uh the men Heap solution I think this trick is worth knowing because it actually comes up in a lot of problems if you're not familiar with this trick I would consider heading over to n code iio and going to the N code 150 list and if you go to the Heap section this is actually literally the first problem in that section will teach you that trick and I have a pretty decent video for that problem okay so now let's get into it the main thing about this problem well there's two aspects it's the BFS the breath for search I have plenty of videos on that so I'm going to be kind of going through that real relatively quickly we use a q in my case I'm going to use a deck in Python I'm going to initialize it with the root because we're guaranteed that the root is going to be non null we can safely do this and I'm also going to declare a Min Heap which initially is going to be an empty array and I'm going to say this is going to be at most size equal to K and then while the Q is non empty we're going to do the breadth for search so for a particular level we want to compute the level sum I'll initialize that to zero now we're going to go through the current level so I'm going to take a snapshot of the length of the Q at this point in time and that's how many times I'm going to iterate so I'm going to have a for Loop for I in range this many times so just going through the current level the reason I'm doing this is because we're actually going to be adding to the que as we go through the current level so that's why it's important to take like a snapshot and that's what this does in Python so now I'm going to pop from the left side of the queue pop left we're going to get a node from that and I want to take that value of the node and add it to the level sum just like this and then I want to consider the two children of this node if they exist I want to add them to the queue it probably doesn't matter which order we add them in but I'm still going to do it left to right so if node. left is non null I'm going to say q. append node. left same thing with the right side and q. append no. write now that we computed the level sum let's go ahead and push it to the Min Heap Heap Q Heap push to the Min Heap this value the level sum it's possible that the size of the Heap became greater than k at this point or maybe it's possible that it didn't either way let's go ahead and check if the length of the Min Heap is greater than K well in that case let's pop from it Heap Q Heap pop from the Min Heap we're almost done with this at this point you might think once we're done with all of this what we can return is the minimum value in the Min Heap at the end of this and in that case what we would do is return this Min Heap at index zero that's almost correct but remember if there aren't K levels in the tree what we actually want to do is return1 so how do we know if there are K levels well the size of the Min heap if it's less than k then we return ne1 cuz that means we never even added K values to the Min Heap in the first place so I'm going to handle that with a Turner operator return ne1 if length of Min Heap is less than K else return the K's smallest integer that's the entire code let's give it a run you can see it works and it's pretty efficient if you found this helpful definitely check out n code. for a lot more thanks for watching and I'll see you soon

Original Description

🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews 🧑‍💼 LinkedIn: https://www.linkedin.com/in/navdeep-singh-3aaa14161/ 🐦 Twitter: https://twitter.com/neetcode1 ⭐ BLIND-75 PLAYLIST: https://www.youtube.com/watch?v=KLlXCFG5TnA&list=PLot-Xpze53ldVwtstag2TL4HQhAnC8ATf Problem Link: https://leetcode.com/problems/kth-largest-sum-in-a-binary-tree/description/ 0:00 - Read the problem 0:30 - Drawing Explanation 6:49 - Coding Explanation leetcode 2583 #neetcode #leetcode #python
Watch on YouTube ↗ (saves to browser)
Sign in to unlock AI tutor explanation · ⚡30

Playlist

Uploads from NeetCodeIO · NeetCodeIO · 0 of 60

← Previous Next →
1 Leetcode 149 - Maximum Points on a Line - Python
Leetcode 149 - Maximum Points on a Line - Python
NeetCodeIO
 2 Design Linked List - Leetcode 707 - Python
Design Linked List - Leetcode 707 - Python
NeetCodeIO
 3 Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
Minimum Time to Collect All Apples in a Tree - Leetcode 1443 - Python
NeetCodeIO
 4 Design Browser History - Leetcode 1472 - Python
Design Browser History - Leetcode 1472 - Python
NeetCodeIO
 5 Number of Good Paths - Leetcode 2421 - Python
Number of Good Paths - Leetcode 2421 - Python
NeetCodeIO
 6 Flip String to Monotone Increasing - Leetcode 926 - Python
Flip String to Monotone Increasing - Leetcode 926 - Python
NeetCodeIO
 7 Maximum Sum Circular Subarray - Leetcode 918 - Python
Maximum Sum Circular Subarray - Leetcode 918 - Python
NeetCodeIO
 8 Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
Find Closest Node to Given Two Nodes - Leetcode 2359 - Python
NeetCodeIO
 9 Concatenated Words - Leetcode 472 - Python
Concatenated Words - Leetcode 472 - Python
NeetCodeIO
 10 Data Stream as Disjoint Intervals - Leetcode 352 - Python
Data Stream as Disjoint Intervals - Leetcode 352 - Python
NeetCodeIO
 11 LFU Cache - Leetcode 460 - Python
LFU Cache - Leetcode 460 - Python
NeetCodeIO
 12 N-th Tribonacci Number - Leetcode 1137
N-th Tribonacci Number - Leetcode 1137
NeetCodeIO
 13 Best Team with no Conflicts - Leetcode 1626 - Python
Best Team with no Conflicts - Leetcode 1626 - Python
NeetCodeIO
 14 Greatest Common Divisor of Strings - Leetcode 1071 - Python
Greatest Common Divisor of Strings - Leetcode 1071 - Python
NeetCodeIO
 15 Shortest Path in a Binary Matrix - Leetcode 1091 - Python
Shortest Path in a Binary Matrix - Leetcode 1091 - Python
NeetCodeIO
 16 Insert into a Binary Search Tree - Leetcode 701 - Python
Insert into a Binary Search Tree - Leetcode 701 - Python
NeetCodeIO
 17 Delete Node in a BST - Leetcode 450 - Python
Delete Node in a BST - Leetcode 450 - Python
NeetCodeIO
 18 Shuffle the Array (Constant Space) - Leetcode 1470 - Python
Shuffle the Array (Constant Space) - Leetcode 1470 - Python
NeetCodeIO
 19 Fruits into Basket - Leetcode 904 - Python
Fruits into Basket - Leetcode 904 - Python
NeetCodeIO
 20 Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
Number of Subarrays of size K and Average Greater than or Equal to Threshold - Leetcode 1343 Python
NeetCodeIO
 21 Naming a Company - Leetcode 2306 - Python
Naming a Company - Leetcode 2306 - Python
NeetCodeIO
 22 As Far from Land as Possible - Leetcode 1162 - Python
As Far from Land as Possible - Leetcode 1162 - Python
NeetCodeIO
 23 Shortest Path with Alternating Colors - Leetcode 1129 - Python
Shortest Path with Alternating Colors - Leetcode 1129 - Python
NeetCodeIO
 24 Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
Minimum Fuel Cost to Report to the Capital - Leetcode 2477 - Python
NeetCodeIO
 25 Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
Count Odd Numbers in an Interval Range - Leetcode 1523 - Python
NeetCodeIO
 26 Contains Duplicate II - Leetcode 219 - Python
Contains Duplicate II - Leetcode 219 - Python
NeetCodeIO
 27 Path with Maximum Probability - Leetcode 1514 - Python
Path with Maximum Probability - Leetcode 1514 - Python
NeetCodeIO
 28 Add to Array-Form of Integer - Leetcode 989 - Python
Add to Array-Form of Integer - Leetcode 989 - Python
NeetCodeIO
 29 Unique Paths II - Leetcode 63 - Python
Unique Paths II - Leetcode 63 - Python
NeetCodeIO
 30 Minimum Distance between BST Nodes - Leetcode 783 - Python
Minimum Distance between BST Nodes - Leetcode 783 - Python
NeetCodeIO
 31 Design Hashmap - Leetcode 706 - Python
Design Hashmap - Leetcode 706 - Python
NeetCodeIO
 32 Range Sum Query Immutable - Leetcode 303 - Python
Range Sum Query Immutable - Leetcode 303 - Python
NeetCodeIO
 33 Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
Binary Tree Zigzag Level Order Traversal - Leetcode 103 - Python
NeetCodeIO
 34 Middle of the Linked List - Leetcode 876 - Python
Middle of the Linked List - Leetcode 876 - Python
NeetCodeIO
 35 Course Schedule IV - Leetcode 1462 - Python
Course Schedule IV - Leetcode 1462 - Python
NeetCodeIO
 36 Single Element in a Sorted Array - Leetcode 540 - Python
Single Element in a Sorted Array - Leetcode 540 - Python
NeetCodeIO
 37 Capacity to Ship Packages - Leetcode 1011 - Python
Capacity to Ship Packages - Leetcode 1011 - Python
NeetCodeIO
 38 IPO - Leetcode 502 - Python
IPO - Leetcode 502 - Python
NeetCodeIO
 39 Minimize Deviation in Array - Leetcode 1675 - Python
Minimize Deviation in Array - Leetcode 1675 - Python
NeetCodeIO
 40 Longest Turbulent Array - Leetcode 978 - Python
Longest Turbulent Array - Leetcode 978 - Python
NeetCodeIO
 41 Last Stone Weight II - Leetcode 1049 - Python
Last Stone Weight II - Leetcode 1049 - Python
NeetCodeIO
 42 Construct Quad Tree - Leetcode 427 - Python
Construct Quad Tree - Leetcode 427 - Python
NeetCodeIO
 43 Find Duplicate Subtrees - Leetcode 652 - Python
Find Duplicate Subtrees - Leetcode 652 - Python
NeetCodeIO
 44 Sort an Array - Leetcode 912 - Python
Sort an Array - Leetcode 912 - Python
NeetCodeIO
 45 Ones and Zeroes - Leetcode 474 - Python
Ones and Zeroes - Leetcode 474 - Python
NeetCodeIO
 46 Remove Duplicates from Sorted Array II - Leetcode 80 - Python
Remove Duplicates from Sorted Array II - Leetcode 80 - Python
NeetCodeIO
 47 Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
Maximum Twin Sum of a Linked List - Leetcode 2130 - Python
NeetCodeIO
 48 Concatenation of Array - Leetcode 1929 - Python
Concatenation of Array - Leetcode 1929 - Python
NeetCodeIO
 49 Symmetric Tree - Leetcode 101 - Python
Symmetric Tree - Leetcode 101 - Python
NeetCodeIO
 50 Check Completeness of a Binary Tree - Leetcode 958 - Python
Check Completeness of a Binary Tree - Leetcode 958 - Python
NeetCodeIO
 51 Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
Construct Binary Tree from Inorder and Postorder Traversal - Leetcode 106 - Python
NeetCodeIO
 52 Find Peak Element - Leetcode 162 - Python
Find Peak Element - Leetcode 162 - Python
NeetCodeIO
 53 Accounts Merge - Leetcode 721 - Python
Accounts Merge - Leetcode 721 - Python
NeetCodeIO
 54 Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
Binary Tree Preorder Traversal (Iterative) - Leetcode 144 - Python
NeetCodeIO
 55 Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
Binary Tree Postorder Traversal (Iterative) - Leetcode 145 - Python
NeetCodeIO
 56 Number of Zero-Filled Subarrays - Leetcode 2348 - Python
Number of Zero-Filled Subarrays - Leetcode 2348 - Python
NeetCodeIO
 57 Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
Minimum Score of a Path Between Two Cities - Leetcode 2492 - Python
NeetCodeIO
 58 Sqrt(x) - Leetcode 69 - Python
Sqrt(x) - Leetcode 69 - Python
NeetCodeIO
 59 Successful Pairs of Spells and Potions - Leetcode 2300 - Python
Successful Pairs of Spells and Potions - Leetcode 2300 - Python
NeetCodeIO
 60 Optimal Partition of String - Leetcode 2405 - Python
Optimal Partition of String - Leetcode 2405 - Python
NeetCodeIO

This video teaches how to solve the Kth Largest Sum in a Binary Tree problem using BFS and heaps, with a focus on time complexity analysis and efficient algorithms. The problem requires finding the Kth largest sum of levels in a binary tree, and the solution involves using a Min Heap to store the K largest levels and iterating through each level of the tree using BFS.

Key Takeaways
  1. Initialize a Min Heap of size K
  2. Push each level's sum into the Min Heap
  3. Pop the minimum element from the Min Heap to maintain the K largest levels
  4. Iterate through each level of the tree using BFS
  5. Compute the level sum for each level
  6. Take a snapshot of the length of the queue
  7. Pop a node from the left side of the queue
  8. Add the node's value to the level sum
  9. Add the node's children to the queue
  10. Push the level sum to the Min Heap
💡 Using a Min Heap to store the K largest levels in a binary tree allows for efficient computation of the Kth largest sum, with a time complexity of n + H * log K where H is the height of the tree.

Related AI Lessons

⚡
Bloom Filters, Explained Properly
Learn how Bloom filters work and their benefits, including tiny memory and blazing speed, in exchange for potential false positives.
Dev.to · Daksh Gargas
 ⚡
Prefix Sums: The Preprocessing Trick That Makes Range Queries Instant
Learn how prefix sums enable instant range queries in arrays, boosting performance in various applications
Medium · Programming
 ⚡
I Thought I Was Ready for the Interview — Then One Simple Math Question Destroyed Me
A simple math question can destroy a developer's interview, highlighting the importance of being prepared for unexpected questions
Medium · Programming
 ⚡
Week 2(Day 10): LeetCode Two Pointers(slow & fast): Remove Duplicates from Sorted Array (Brute…
Learn to remove duplicates from a sorted array using the two pointers technique, improving from brute force to optimized solutions
Medium · Python

Chapters (3)

Read the problem
0:30 Drawing Explanation
6:49 Coding Explanation
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →