Binary Tree Vertical Order Traversal - Leetcode 314 - Python

Key Takeaways

Hey everyone, welcome back and let's write some more neat code today. So today, let's solve the problem binary tree vertical order traversal, not level order traversal like you might be more used to. In this problem, we're given the root of a binary tree and the root might be null. So keep that in mind, but we want to return the vertical order traversal of the nodes, meaning from top to bottom, column by column, and we want to return the values. So in this example, we see the root over here and we see that in this column, let's call it column zero, we have these two nodes and then we have the nodes written three and then 15 in the order that they appear from top to bottom. But that's not the first array that we're going to return. You can see here in the output that the first one is the leftmost column. That does make sense. We return this column, then this one, then this one, and then this one. And the leftmost column, let's call it at column -1, is just 9. And then over here, column 1 is just 20. And column 2 over here is just seven. And we return them in that order. This is the first array, second array, third, and fourth. We return them in the form of a nested list. So that kind of gives you an idea of what the vertical order traversal actually is. But this last line might confuse you, which is to say, two nodes that are at the same row and the same column, the order of them should be from left to right. Because if they're at the same position, it might be kind of ambiguous. If you don't know what that means, let me just draw out a little picture to show you. Let's say we have a root node, a left child, a right child over here. Sorry, I kind of didn't draw that on the same level. But then let's say this guy has a right child. This guy has a left child. Now these are considered to be at the same column. Let's say zero and this is negative one and this is positive one. Cuz when I'm here and then I have a right child, I'm going to take my column and increment it by one. So this guy which is on level two, this is level one, this is level zero. This guy is at column zero. But this guy when we go left we take the current column and decrement it by one also bringing us to zero. So this node is on the same row and same column as this one. So it's ambiguous because this is obviously one column. This is the other column, the middle column. And then we have one column over here. With the middle column, what order do these nodes appear in? Well, this is the first one. But between these two, it's ambiguous. That's why they tell us we will read them from left to right. So this is second, this is the third one. So that's what they mean when they ask us this part. So now that we have a bit of an idea of what the problem is asking for, which honestly with this problem is one of the hardest parts. So don't feel too bad if you struggled with it. But now that we have an idea of what they're asking us, how do we go about solving this problem? Well, typically with tree problems, you don't really have to get too creative. Most of the time it's probably going to be related to DFS or BFS. And I believe this problem can actually be solved both ways, but I think the BFS approach is a lot more intuitive. And I'll tell you why. Think about what we're doing with this problem. Each of these columns is going top to bottom, like the individual nodes in that column. If there's a tie, we want to go left to right. Well, BFS basically gives us both of these properties. BFS, which is actually a level order traversal, not vertical. It's going to go level by level. First level, then the second level, then the third level. So you have that top tobottom component of it, but also within a level, we're going left to right. Now, we could go the other way if we wanted to, but with this problem, it makes it pretty clear that we want to go left to right because with these two, we want this guy to go first and this guy to go second. So with that we can actually solve this problem relatively simply and as we do the BFS we just want to maintain the the current node and we want to maintain the column of every single node because we already know we're going to go top to bottom we're going to make sure to visit this level after the previous one and this one after the previous one so that this node will be added first and then these nodes. But we also want to be able to group these nodes together. And we'll do that by maintaining the column of each node. And then we'll be able to know that this node is not in the same column. This node is also in a different column. That's more or less the intuition. Now, one thing to keep in mind is how are we going to build these lists of lists? In terms of grouping nodes together within a certain column, it's not as straightforward as building the list of lists because we don't know the range of columns that's actually available to us. So, you know, you could say this is zero, but how do you know that -1 is going to be in bounds of this array, the outer array that is? Well, that's why it's probably better to use a hashmap for this problem where we take a column. So like this one, the index of the column and map it to an array or a list. This makes it pretty straightforward for us. And then at the end, we can kind of collect those lists together and then return it in the form that we actually want. So I think that's enough for us to now get into the dry run. So let's say we're given a tree that looks like this. And I'll go ahead and draw the hashmap as well. will map each column to let's say the list of values in that column. And I won't draw out like the whole Q BFS part. If you're not familiar with BFS, I highly recommend checking out some of the resources on neatcode.io. Those will walk you through that pretty in-depth and you'll definitely want a good understanding of this algorithm. It comes up quite a lot and if you understand it, this problem becomes pretty trivial. Let me show you what I mean. So let's say we start here and let's say that that's column zero. We're going to go ahead and map it in our hashmap to zero. And then we're going to create a list here. And the first value in that list is going to be one. And then we're going to go to the two children that do exist. We'll end up adding them to the queue as well. This one is going to be at -1. This one is going to be at positive one. We'll go left to right. Pop this one. It's at column 1. And we will map that to two over here. We'll do the same thing after popping this. We'll map it to one. And the value of that is three. So we'll do that. This one didn't have any children. This one does have two children. Left child is going to be at column zero. Right child is going to be at column two. Let's go ahead and take the four. This time it's at a column that already exists. So we will take that four and append it to this list over here. We get that four. Next we do this one and it's at column 2. So here we will add five to that column. And then this one does have a child. left child is going to be at 2 minus one column one. We'll take this six and it's over here. This is the column and we'll add it to the list over here. And then we're pretty much done. There's no more nodes for us to do. So these are the lists that we have. Now we want to collect them in a specific order. We want the minimum column to go first and then the next one, then the next one, and then the next one. So what you could do is just find the smallest column in this hashmap and then just keep incrementing by one until you can't really go any further until we get like a key doesn't exist. Um another way to do it though would be as we're doing this maintain what's the minimum column that we have seen so far and what is the max column that we've seen so far and then you know you can iterate from this one to this one cuz the range of course is going to be contiguous. we don't expect like one of these columns to just not exist, then our tree would be like non-ontiguous. It would be kind of weird. That's not really possible. Um, so then we can just go from negative 1 to two and then just keep collecting each of these lists and then add it to an outer list and then that is what we end up returning. So this way we will visit each node once, we'll end up adding each node to the hashmap at most once. So space and time complexity is going to be linear. So with that said, let's code this up now. So the first thing I'm going to start out with is actually the case where the root does not exist because that is a possibility. And in that case, we can just return an empty list. There's no need to do any sort of traversal. Otherwise, we're going to have our Q, and it's going to be a double-ended Q in Python. And I'm going to initialize it with a tupil, which is going to include the root node, which now we know is not null. And the second is going to be a number which is going to correspond to the column of that node. And like I said, I'm also going to maintain what the minimum column and max column are. That's going to make things easier for us at the end. And initially, we can say that these are both zero because we know that definitely the zeroth column does exist the way that we've defined this. And lastly, we're going to have the hashmap, which is very important. Let's just call it calls columns the plural. And I'm going to use a default dictionary in Python. If you're not familiar with this, highly recommend checking out Python for coding interviews course. It'll walk you through exactly how to use this. But basically, it's a hashmap where the default value is going to be a list in this case. That's the way I've set it up. And we're specifically going to map each column index to the list of values of that column. So then we can return them at the end after we've converted it to a list of lists. So now let's get started with the BFS. while our Q is non- empty pop from the Q and we're going to get a couple values. We're going to get the node and the column. Um I guess this is a good point to update our min and max column because every node is going to be pushed and popped. So we can say our min column is going to be the min of itself as well as the uh column that we're given. And then we'll have the max column which is going to be the max of itself and the column. That's just a little bit of bookkeeping. But the next part is where we take now the value of this node and add it to our hashmap using the column as a key. So calls the plural and then we'll use the current column that we have here. And then to that we're going to append the current nodes value. And then after that we can just check our two children. If my left child exists I'm going to do something which is um taking to the queue. We're going to append the tupil, the left child, and the index of that left child. Well, the column specifically. And this is kind of the important part. We're taking the current column and decrementing it by one when we go left. And I'll copy and paste this cuz the next part's going to be pretty similar. When we go right, we're going to append, of course, the right child, but then we're going to increment the current column. So that's probably the important part of this algorithm here. Now, after that's done, we want to return, but we can't just return the hashmap. We have to return it in the form of a list. I'm going to take advantage of list comprehension in Python. I also cover this in the Python for coding interviews course if you're interested. But what we're going to do is just iterate over uh the range of columns. So, from min column to max column. Let's say for CN range, min column to max column. This is non-inclusive in Python. So I'm going to add a plus one there. So we're iterating over the columns in the order that we want them. And then I'm just going to take from the columns hashmap get the column at the current index. And then we'll add that to this list. So we'll have them in the order that we want and it'll also be in the form that we want. So let me go ahead and return this or sorry execute it. And you can see here it works and it is very efficient. I don't think there's a big difference between 3 milliseconds and this one. The overall time complexity is definitely the same and this is the optimal solution for BFS. If you found this helpful, check out neatcode.io for a lot more. Thanks for watching and I'll see you