Construct Quad Tree - Leetcode 427 - Python

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

Key Takeaways

The video demonstrates how to construct a Quad Tree, a tree data structure in which each internal node has four children, using Python and the Leetcode 427 problem as an example. It covers the definition of the Quad Tree data structure, its construction using a depth-first search approach, and the implementation of the solution in Python.

Full Transcript

hey everyone welcome back and let's write some more neat code today so today let's solve the problem construct a quad tree so we're given a square Matrix maybe something like this one so it's n by n and we actually want to convert it into a tree but not just a regular like binary tree actually a quad tree where every single node in the tree will have four children except of course for leaf nodes maybe like this one this one doesn't have any children so in this case our node is going to look something like this where it will have a value in this case I think values are just going to be either 0 or 1. it'll also have a field to indicate whether it's a leaf or not and will have four pointers for each of the four children where each of the four children will have a spot actually and this brings us to what we're actually trying to accomplish with this grid so given a square grid like this one the root is not going to correspond to any of these cells our root node of our quad tree is not going to be any of these cells but the four children of each of these roots are going to correspond to a quadrant of this grid so actually the root node can kind of be thought of as the entire grid and then it will have a child for the top left portion of the grid so think about it if this is an N by n grid how are we going to define the top left quadrant probably it's going to be n divided by 2 in height and N divided by 2 in width so that's how we're going to define the dimensions and we'll have one for the top right one for the bottom right well bottom left and one for the bottom right and recursively actually for each of these quadrants we can break that up as well you can see they've kind of Illustrated that to us over here on the top right you can see this one is broken up into quadrants as well so recursively that's what we're going to do for each of these squares we're going to recursively break it up again and again into quadrants until we can't do so anymore maybe we get to the individual cells and then for each of those individual cells we actually will be able to fill in a few more of these fields we'll be able to fill in that value so for this grid cell it'll be a one for maybe this one over here it'll be a zero and each of these of course will actually be a leaf so we'll need to set Leaf to true but there's one last shortcut where sort of required to take which is that think about this quadrant over here all of the values are one so we probably don't need to break it up further when we have a node we can kind of just prune this that's usually the word that's used which is basically to take a shortcut here and say that since all of the values here are one we don't need to take this quadrant and actually bring break it up we don't need the children we can say that this is a leaf node and all the values are going to be one anyway so we can just have a node like that so taking this entire thing the resulting tree would look something like this where we have a root node and then each of these four quadrants this is maybe the top left I'll kind of color code them orange will be for bottom left red will be for bottom right and then for top right I'm gonna make it blue because this one actually we can break up into four more quadrants top left is orange top right is white bottom left is blue I'll use like a purplish shade bottom left is blue and bottom right is purple so this is what the tree would look like breaking this up because this one corresponds to this we don't have to break it up any further the way we would know that is probably by running like a loop over this portion of the grid to see that all the values are the same so we don't need to recursively break that up any further the last thing is just a bit of math on how we're actually going to Define these quadrants we know that in terms of Dimensions if this is n this whole part then this part is going to be n divided by 2 and then when we take this part and then break it up into this portion well that's going to be n divided by 4. so basically we'll be taking whatever value we have and dividing it by two each time to get the dimensions at least to get the positions though because we know that these two have the same dimensions but the positions are different this one let's uh to keep it simple let's define each of these quadrants based on their top left position so for this one it's always going to be the origin let's say 0 0 but for this one over here it's going by the row and the column the row here is going to be the same but the column is basically going to be n divided by 2 plus the origin column so it's going to be 0 0 plus n divided by 2 to get the origin for this guy its column is going to be the same as the origin but its row here is going to be the row from here plus n divided by 2 and lastly to get the origin over here well the top left of this quadrant at least will have to get the row of the original plus n divided by 2 and same for the column we'll have to say column plus n divided by 2. so that's the bit of math now in terms of time complexity in the worst case let's say the grid Dimension is n our tree we're going to have four nodes in the worst case every single time and we're going to keep breaking this up recursively now let's say the dimension here was n well we're going to divide it by 2 every time so here we're going to get to n divided by 2 down here we're going to get to n divided by 4 and we're going to keep doing that until n is equal to one so the height of this is going to be log n now in the worst case we'll have like a leaf node for every single position in the grid so the total number of leaf nodes we could have is going to be N squared so you might think that that's the time complexity but you also have to remember that at each level in the tree we are iterating over the entire tree because think about it when we have the original grid and then we break it up into four quadrants we have to check this quadrant do they have all the same values we have to do the same thing for this quadrant the bottom right quadrant and the bottom left quadrant so we have to do that here so the time complexity of that is also N squared and doing the same thing at the next level will have smaller quadrants but we'll have to still do that in the worst case for every single one so every single position in the entire grid that will also be another N squared so we're going to have log n levels in this tree for each level we're doing an N squared operation so the overall time complexity is N squared times log n in this recursive so solution so now let's code this up okay so like I said I'm gonna do this recursively so I'm going to define a DFS we definitely want to pass in the dimensions of our current portion of the grid and we also want to pass in the top left coordinate so I'm going to say row column that's what these stand for I'm going to pass in the top left using these two coordinates we know our main base case is that if all the values are the same so let's try to figure that out I'm going to have a variable which I'm going to call all same I'm going to set it to True initially and then I'm going to create my nested for Loop to iterate over the entire Grid it's a square grid so it's pretty easy to iterate over just have to have a nested for Loop going n times and we want to know is the top left position of our grid of our portion of the grid that we're checking at row column coordinates equal to the next position in this grid we're just trying to iterate over our current portion of the grid which is n by n so to get the coordinate of the next position we're going to say rho plus n and column plus n so if all the values are the same then we don't really want to do anything but if we find any pair of values that are not the same then we will set all same equal to false and then break out of this Loop once we have either iterated over the entire portion of the Grid or broken out of it then we want to check if all same is still true then that's our base case that means we have a leaf node now what is the value of the leaf node going to be that's the first parameter that we pass in it's going to be the value in our grid at the top left position because all of them are the same and next is it a leaf node yes this is going to be a leaf node and then we pass in the four children they're implicitly going to be null anyway so for a leaf node that's what we would want so we don't really have to explicitly say that all of them are null we can just implicitly assume that now you might be thinking this is the base case where all of the values are the same but what about the base case where n is equal to one well we don't have to explicitly Define that case here because actually that's going to be covered by this piece of code anyway so we don't have to worry about that this is our only base case we can think about it like that at least so otherwise we know n is not equal to 1 and all of the coordinates are not the same value so we're going to set n equal to n divided by 2 integer division in Python and then we want to recursively run DFS for each of the four children nodes so for the top left we're going to run DFS we're going to pass in our new n value that we just computed over here and we're going to pass in the row and column since it's top left it's going to have the same top left coordinate as the one that we're currently at but I'm going to copy and paste this because now we're going to get to top right which is going to be a bit different the row is going to be the same for the top right portion but for column we're going to add to it the new n value that we just computed which is half the length of the previous n value so this will give us the top right coordinate so this will give us the top left coordinate of the top right portion of the grid now I'm going to copy and paste this and do it for the bottom right and bottom left so just to rename these now bottom left is going to be the column staying the same but the row is going to be different we have to add n to it we're going to go half that distance and bottom right is going to actually be updating both of the row and the columns so we already have column plus n and for row we're going to say row plus n now we have the result of the four children which we need because now we're going to create a node for the current coordinate that we're at and we know it's not a leaf node so the value that we give it doesn't really matter I'm going to give it a zero you could give it a null if you wanted to it doesn't really matter and for is leaf I'm going to say false we know it's definitely not a leaf because it has four children and these are the four children of that node so let's pass them in top left top right bottom left and bottom right make sure you pass them in in the same order that they have defined up here and this newly constructed node is exactly what we're going to return so let's do that and now outside of this DFS we need to actually call the DFS and what we're going to pass in for n is of course going to be the dimension of the grid and for row column we're just going to start at the origin which is 0 0 that's going to be our top left coordinate so now let's take this and run it to make sure that it works oh whoops I had a very dumb typo sorry about that here we're not adding n we're adding the I and J that's the whole reason that we're iterating over the grid because we want each of those coordinates I'm really sorry if this was confusing now that we've run it you can see that yes it does work and it's pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out neetcode.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon

Original Description

🚀 https://neetcode.io/ - A better way to prepare for Coding Interviews Problem Link: https://neetcode.io/problems/construct-quad-tree 0:00 - Read the problem 0:50 - Drawing Explanation 7:00 - Coding Explanation leetcode 427 #neetcode #leetcode #python
Watch on YouTube ↗ (saves to browser)
Sign in to unlock AI tutor explanation · ⚡30

Playlist

Uploads from NeetCodeIO · NeetCodeIO · 42 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
 ▶ 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 construct a Quad Tree, a tree data structure used to efficiently store and retrieve grid values, using a depth-first search approach in Python. The Quad Tree is constructed by recursively dividing the grid into four quadrants until individual cells are reached, and it has applications in systems design and grid representation.

Key Takeaways
  1. Define the dimensions of the quadrants as n/2 in height and n/2 in width
  2. Break up the grid into quadrants and recursively divide them into sub-quadrants until individual cells are reached
  3. Apply pruning if all values in a quadrant are the same
  4. Fill in the value of each grid cell and set the leaf flag to true
  5. Construct a Quad Tree node with left, top, right, bottom, left_child, right_child, val, and is_leaf properties
  6. Initialize a Quad Tree with a grid of size n
  7. Iterate over the grid to construct the Quad Tree node for each cell
  8. Run the Quad Tree construction code to verify its correctness
💡 The Quad Tree data structure can be constructed using a depth-first search approach, which allows for efficient storage and retrieval of grid values. The construction of the Quad Tree involves recursively dividing the grid into four quadrants until individual cells are reached, and pruning can be ap

Related Reads

📰
The Minecraft anvil is a tree-cost optimization problem in disguise
Optimize tree costs in Minecraft using graph theory and algorithms, just like the anvil repair system
Dev.to · Mark
 📰
KMP Algorithm (Knuth-Morris-Pratt): The Smart Way to Perform String Matching in O(N)
Learn the KMP algorithm for efficient string matching in O(N) time complexity and improve your coding skills
Dev.to · Jaspreet singh
 📰
Every Backtracking Problem Is the Same Three Lines. I Just Couldn't See the Tree.
Master backtracking problems with a simple three-line approach to improve problem-solving skills in coding interviews and challenges
Dev.to · Alex Mateo
 📰
DSA From Zero to Hero #3: Sliding Window (Fixed Size) Explained With a Java Example
Learn to solve subarray problems efficiently using the sliding window technique, a crucial skill for software engineers and data scientists
Medium · Programming

Chapters (3)

Read the problem
0:50 Drawing Explanation
7:00 Coding Explanation
Up next
Stump Grinder Carbide Wheel Grinds Hardwood To Chips
Innoforge Studio
Watch →