Amazon Software Engineer Interview: Print Left View of Binary Tree

given a binary tree print the left view of it [Music] welcome everybody to another mock interview with exponent today we have russian with us russia would you like to introduce yourself before we get started absolutely so hi everyone my name is roshan i currently work as a senior software engineer at amazon and i have like five years of experience working with multiple firms including deloitte and now working as a engineer at amazon so we operate like i mean the team which i work work here at amazon we operate at a massive scale like we our team is responsible for generating tracking ids for each and every package which is bought by our customers in this planet earth so we operate at a massive scale and especially during those times when you know we are at kobe situation and uh everyone is trying to purchase products online you know staying at their homes and purchasing products be it grocery items or be it anything for that matter right so that's what um like currently we are at um you know we are operating at a peak scale but yeah having said that i have i i have a huge i mean i i have interest in solving problems and helping people who who want to grow in their career be it cracking coding interviews and stuff like that so yeah that's all about me and i hope that one day i will create a impact which is going to you know help people in this earth that's that sounds great thank you so much russian let's dive right into it so the question for you today russian is given a binary tree print the left view of it and the left view is the set of nodes that are visible when the tree is looked at from the left side okay okay got it so can you just uh explain me what that left view means like i'm aware of binary tree i i know the binary tree data structure but can you please help me understand uh what is the left view sounds good so let's say that this is your binary tree okay this is your root node these are the two two leaves all right now uh i don't know which is your left but let's say this is this is defined as left alright if we look at the tree from this angle from the left side what are the nodes that we're going to see and bear in mind that if there are two nodes on this level you're not going to be seeing this one because it's going to be blocked by the thing in front of it so that's what a left view means okay so say suppose if i have a root node and then one and two as sorry if one is the root node and two and three is its uh child node so i have to print one and two yes suppose if i if i only had one and then three but no two then my output should be one and three is that correct exactly that's exactly correct yes okay wow awesome okay so i'm just thinking of how i could solve this problem first of all uh i am pretty much aware that um any um any by any binary i mean binary tree related problem they have three types of traversals one is uh in order pre-order and post order so i'm just thinking of how i how i would be approaching this problem right before that i'm just also wondering yeah uh i have i have a i have some follow-up questions what can we have uh an empty tree if that's the case then what will be the what should be the output like for example if if if i were to just pass null as the root node so should i simply return null or yeah i print minus okay if your tree is null return null okay so that's something which i wanted to ask and uh is this a regular binary tree i i think uh even if it's a binary tree or binary search tree i think the output shouldn't matter right because yes okay so i think um yeah i think i don't have any uh any other clarifying questions i think i'm pretty good with the question okay so basically i'm gonna print one here so this is the root note right so what i know what i know already is we have like in order then we have pre-order and then we have post order but however since our use case falls more into pre-order where we print the root note first followed by the left tree and the uh sorry the left left subtree and the right sub right so i'm gonna use pre-order traversal here the reason being that i want to give more priority to the root node so i'm going to start with root first followed by left node followed by root right right so that's going to be my um strategy however i don't want to print the right note like basically i want to ensure that um at each level basically like for example this is level one okay and then we have like yup sorry yeah this is level two what i need to ensure is if i have printed the first node at level one i don't want to print any other nodes or in other words like say suppose if i go to level two if i have already printed a node at level 2 i don't want to go to i don't want to print the print another note right so for example say suppose if in the third level we had um only 6 as the right right right subtree then this would be level three and since two uh doesn't have any right uh it doesn't have left and right sub three and three only has the right subtree and that's the first node at level three i'm gonna print this so then my output would look something like one two and six so in simple words i'm just gonna find the uh i'm gonna go at each level and see the uh the first node so yeah that's what i'm thinking okay sounds good okay so yep let's first create some [Music] uh i'm gonna say in data and every node will have left and right um right child and let's had a constructor in here [Music] same this dot data is equal to data and um i'm just gonna initialize the left and right um child to null okay so this is uh just a signature i'm just gonna make this public okay so so let's create a a a sample tree so node root is equal to new node of 1 and then i'm going to say root dot left is equal to a new node of 2 just copy this and put it here and say root dot write is equal to 3 so basically i'm just trying to create a replica of this one one two three and later on we will extend it to six as well okay sounds good so now um let's um let's create a list of integer and we say that result is equal to a new array list of i'm gonna store all my uh left view in the result and i'm gonna finally print it okay okay so um let's create this okay so this this left you will take the root as the input and it's oh by the way it will also take a list which will contain the result and yeah so once we let me create an instance of this instance of dot um left view of i'm gonna pass in two parameters one would be the root for which we have to print the left which we have to you know see see the left view and store them in this array list which is going to be result and once we have the result we just want to print it so okay so okay so just to summarize this code basically we have created a a tree here and uh we are creating the result which will store the result of the left view so for example i wanna like if i pass one two and three as the input i wanna store one and two in my list and then finally print this list that's it right and then yeah that's all i have done and this is the signature basically this left you is taking uh uh like taking two parameters one is the root of the tree and the result where it's gonna store it yeah yeah okay so if um if the tree is empty we just wanna like we just wanna return it so we'll start with the base condition if like root is null we simply return it because um we don't want to do anything with it because like if if if the list is like that if the root is null then we simply return an empty result so this will this will anyways contain the answer because this is this has already been initialized as empty result right so okay now um what we want to do is if we find um [Music] we also want to calculate the level right um okay so my root would be at level 0 i guess yep so i also want to have something called level where um where you know when i make a recursive call i keep incrementing the level and um see uh if i have reached a level and it's first node so what i'm gonna do is i'm gonna say my root is at level zero okay so whenever i see whenever i see a node uh which is uh which is at a level and it has not been printed yet so i want to add that element to my list so in this case it would be one now i'm thinking about the next case where if uh so level plus one which would be one so let's say this is um okay let's let's do one thing let's let's take the root as level one itself here so this is level one so one would have wouldn't have been printed so i need to add that to add that node to my result and then increment the level so it would be level two now okay then i wanna see if we have already printed any element at level two so we since we wouldn't have printed we want to add uh you know two to the result but when we when we reach a point three we again see if we have if we have already printed any node at level two and since we have already printed it we don't want to include this element right yeah so let's do one more thing let's um basically we also want to have some max uh max reached so far and let's initialize this somewhere here max level and let's initialize this to [Music] 0 because um 1 is greater than 0 and we want to print the root okay so we want to print a 0 y 0 because um let's say we are at max level zero so if um if this level is greater than max level so we know we know that we have reached a point where we wanna add the element to the list basically result dot add of that uh root dot data something so then uh when when my level is a 2 and my max level is also like my max would be 1 so since 2 is greater than 1 i can add 2 here but for 3 since we have already incremented max level so 2 greater than 2 would be false and then i will not have to add root or data so [Music] i'm just gonna say if max level is less than level then um say result dot add of root dot data and um i'm gonna say max level is equal to level so that i don't end up adding three and then i'm gonna just uh print this root dot left and then level plus 1 because i'm just incrementing it incrementing at every recurs at every recursion and the result is going to be the same and same thing i want to repeat for the right subtree yeah this one so if okay so i'm just doing a dry run of this approach so we pass one here so level okay so in in the first in the first iteration it would be zero less than one i'm gonna add uh root dot data to my result which would be one and then i'm gonna say max level is equal to level so now max level is one okay root dot left so we come here and level plus one so level plus one would be two so one less than two is true and um i'm gonna add root dot data so two right and then so if uh then again true dot left would be null so it will return and then root dot write which is again null so it would return and then it would check the right subtree which is this one now so root dot write it would come here and check uh max level would be um 2 by 2 by this time because we have initialized here and not inside this function so yeah so 2 less than 2 right because 3 is all 3 is also at level a 2 so 2 less than 2 is condition false so we will not be adding the result so finally um yeah again if you check the left subtree and right subtree of three which would be null and null and finally it will return the result which we are printing here okay okay okay so let's try this out i hope this works um but yeah okay so if i run this code oh line 19 is not a statement hmm it's just there's a comma there oh i i didn't wanted to print a line i just wanted to say okay okay so let's further extend this code a bit like um i'm gonna say [Music] three threes right child to be six so root dot right dot right um is equal to six and i'm expecting the output to be um one two and six okay so yum oh there you go yeah so great now i think i i also wanna just check one more thing instead of if i just pass a null here i just want to see if it's still working okay i mean it's not printing anything basically yeah empty list yeah okay that's great so what's the what's the complexity of this solution um basically it's the in the worst case we are try we are iterating over all the nodes of the tree so o of n where n is the number of nodes in the tree so yeah and uh we are not using any extra space except for the result like if we were to ignore this list and simply print the answer here that would still work right because this result is basically containing the result like you know the element that we want to print like in case if we want to you know uh uh remove it all together we can simply print it here so we we don't need this extra space as well got it yeah that would be that would be good space optimization so is there is there any optimization that you can make to the time complexity of this of this algorithm i understand so basically why do why do i have to visit the right subtree if i have already found a node which has added added in the list so do you understand what i mean so yeah say suppose we are at level one right and um if i have encountered a node which has already been added to this result set then i don't even have to visit three oh no i still have to do that the reason being if i don't visit it i will not be able to encounter six because the the reason why i'm able to encounter six is because i have visited three now you think if i don't do that if i don't do that i i mean my my my solution would assume that there was only one and two but there was no notes at level three at all so yeah i wouldn't do that i wouldn't do that yeah okay yeah but so yeah i don't have any um time optimization here yep got it okay um and then maybe we should implement the space optimization that you mentioned what we can do here is just remove this result because we don't need it here and just print it here so we say click just this thing system.print and then just add root.data plus some spaces in here and then we don't pass we can remove this all together and we just say instance dot um left view off and now just pass the route and the level which is one okay and we can remove this result as well and so uh some more so we don't need this instance anymore okay so yeah so we we don't need that uh extra space now we just print it as and when we encounter so now the output should still remain the same oh no uh left view result oh okay in the recursive call also i will have to remove the result here yes nice let's add something add a little extra spice to the question so now what if i ask you i'd like you to print the left view of the tree as well as so the left view and the right view so you're printing basically an outline of the tree yeah right so the left view is one and two so if i were to print the right view of the same tree it would be one three and six and what if what if we want if we want the outline of the tree let's say we wanted to print like two one three six it could be a bunch of stuff in the middle but we don't we don't really want that okay um i think um outline of the tree so for example if i if we were to have four in here and five in here let's add some spacing okay so one two three five seven and then eight okay now the output that you're expecting is four two one three eight that's right okay okay um but so uh one question here like a five and seven is also an outline right like uh do you understand what i what i mean yes it's an outline of the of a subtree of the main one yeah so okay so i think i understand where you're getting with this basically if we wait to have something like this like one moment and i move this a bit okay now if if we had some some nodes in here like nine so nine and then one and then so okay let me just put it this way so one two three four five six seven eight okay okay now uh four has uh some more uh left and right subtree so one and two then three and four four five four seven we have five and six and four eight hundred now the output would be one sorry yeah starting from the from the left most note so one uh four two one three eight and eight yes or do we also want to print the last line all i just wanted to know is are you interested in the uh in the bottom edge of the triangle no not interested in the bottom edge of the triangle okay okay so basically this seems more to me like a combination of left view and the right view excluding the root excluding which root okay excluding which good question so basically the the root which is here so i mean what what i mean by that is uh i do i don't want to print something like 1 4 2 1 and then um 1 and then 3 eight eight right because uh if i'm printing from the left view i just wanna ensure that one is printed only once or if i'm printing printing it from the right view i just want it to ensure that we have root only once i don't i don't want this yes yes so what would uh can you just type out what the output would be for this tree that you've you've drawn no i mean same thing except that yeah got it yes yeah okay so i think i can just uh make some changes here to print this okay um what we have what like if we were to leave the solution as it is so what would we get so far so we would get this part right um okay by the way um we are printing it so this this particular solution is printing the element from the root right so we are printing one two four and one but we want it to be printed from the left i mean starting from here and then go all the way to the top yes okay so let's first change that a bit so i'm just gonna move this this code here and okay now why why did we do that because we wanna go all the way down so this root dot left will you know keep it will keep uh recursively going all the way down until it reaches this point and then we want to do this uh calculation that we did earlier right and then okay so let me just uh see uh for the input that i passed so it was one two three and six how did i i just deleted okay let me just uh draw this again so we had like one and then we had two and then three and then six so now the output would be two uh okay let me think all the way okay so two one and six yeah so two one and six yeah so that's what i'm expecting so let's see uh two and six uh why didn't i get one max level okay because because this is this would be one okay because i'm not okay by the way i i still don't need it because as as as far as this this problem is concerned i don't want this root to be printed because i will anyways take care of it in the middle so that should be fine yeah okay two and six so two here and six here okay so however i'm just wondering one more thing um do we really need to consider the left view of this one because this will anyways be taken care by the right view so we start so if okay for for this input it would be like um 2 one uh three and six right yes right okay so i don't have to worry about the uh right view anymore because this will anyways be taken care by the right view method so like something similar so we just create another method in here say void off right view and just change um right yep and then root dot write so [Music] so root dot left would print this and do group dot right this i'm just wondering about the max level now so max level is zero i want to ensure that uh before i make a call to left view and right view max level is initialized to zero again that i can that i can take care here left view up there okay let's um let's change this to something meaningful yeah so let's call this as tree okay so um tree dot max level is equal to zero and then tree dot um left view of our root and level to be 1 and then [Music] 3 dot right view but i want to ensure that this max level is initialized to zero again okay now i don't wanna pass root but instead uh oh no oh no no because i have taken care of or right here itself so yeah level plus one should be suffice okay so what would where am i printing the data so here okay so we go all the level okay so we go all the level down so we print one and then oh okay max level is less than level so by the time it reaches here um level would be uh one two three and four um and so we are initializing max level to max at that time itself so um actually this won't work because um we are already initializing max level at four so every time no matter it reaches uh level three level two or level one uh it would never get printed because we have already initialized max level at four so all the time this condition will become false do you understand what i mean yeah okay actually let's stick to the older approach itself where we say we wanna we wanna print one one two four and one and then so one we go one two four one two four and one okay so that would still remain the same and then the right subtree so that would be one um three eight and eight okay so we are good at right subtree but uh not for the left subtree so we just have to take the reverse of it yeah so that would be one four two and then one and then combine three and eight here okay man yeah okay this is getting really complicated but yeah let's let's stick to the same plan let's move this code again back here we don't wanna change this okay so same thing here okay by the way let me change this comment so i don't forget it next time yep so this looks good so um okay let's let's try to see what's the output we are getting so far okay so if i were to run this code what is it giving me so far okay awesome so it is saying uh one two looks good and then 136 awesome okay so uh this part is clear all we just need to ensure is we are not passing the root here right so we just say root dot left so it would be two one three and six i hope it works okay awesome so now our problem will not like our solution will not work because we wanted um [Music] like go all the way go all the way to the left yeah then go i mean traverse all the way to the root and then start from root entering the right so we don't have to change anything here this looks absolutely good except that um when we are printing this this this data here uh we want to reverse it do you understand what's going on got it yeah yeah right so how do how do i do that okay let's bring this um bring it back yeah yeah bring this back again and just say oh let me let me add this guy here because okay okay let's comment this out for now and uh do okay let's keep this still like we just same thing here and same thing here again just okay now again comment this out and just use this code in here okay so um okay now before um before i call um yeah before i call the right view i just want to ensure one more thing it's just that collections dot reverse of oops or levels of list yeah and then i can just use reuse this code here okay and i'm just gonna say item okay so yeah so what it look like how does the code look so far like just the same thing except that before we before we pass this list to the right view we just wanna reverse this list yeah so that so for example if i have like uh two four and one printed i will just have one four and two makes sense and then start from i don't have to do that here because this one already works fine to me so yeah okay so let's let's see if this works um i think this will this will give the same output oh yeah so but but yeah let's tweak this a bit so one two three and then i want four five seven and eight okay so let me add some data in here so i'm gonna say this as four and same thing here but root dot right of one two four and five and copy this here but this time right right and then left and then right yeah so root dot right off left and root dot right off right here it would be seven and eight okay so seven here and eight here so what's the output expectation so it should be four two one and then three and eight four two one three eight yes okay so let's give this a try nice very cool so let's let's uh delete all the stuffs which are no longer required okay yeah awesome yeah i think this is great i definitely threw you a hard one um this so for for the viewers these are generally mock interviews and russian just did fantastically in the mock part of it so we decided to spice things up a little bit and uh throw this slightly more challenging variant of the question in there you you definitely i threw a wrench into the process and you wrangled that wrench and turned it into something fantastic so this was great what were your feelings about the interview yeah i mean the left view looked pretty straight forward but this one actually i haven't like frankly speaking i haven't encountered such problems in my power i mean uh during my uh interview preparations yeah so this was really yeah i'm actually feeling proud of myself like i'm able to solve it i think it should be yeah um there have been a couple of times when i so i've been on the in on your end of the interaction and have had the same thing happen where i feel like this interview is going great and i'm 20 minutes into it and i've solved it and then that just leaves more room for us to face more challenging questions which isn't necessarily a bad thing um so that's something that i've been doing as an interviewer as well just it just helps get more signal from someone and and yeah just even if people my advice would be even if you don't get the right answer we just want to see how you think and you voiced out your thoughts throughout the whole process um we're very clear in what you were changing why you are changing it uh which which definitely helps in getting signal even if the end result isn't isn't what the correct answer is which in this case it was so it was great right so just one thing like for people who are you know viewing this uh video right now or whoever has an upcoming interview i just wanted to help you guys understand that in case um if you if you receive the question from the interviewer like first thing that you guys need to do is ask enough clarifying questions like you know as um as i started with asking like if the root node would be null or if we are only interested in binary tree or binary search tree because anyways this uh this will not change the output but still it's always good that we ask clarifying questions so that's the one thing which i you know uh improved over a period of time and i would highly recommend people who are watching this video to ask clarifying questions and don't try you know directly jump into the solution and start coding uh end a equal to b or something like that so once you have a thorough understanding of the question then try to uh talk to the interviewer as much as possible because uh one thing that you guys need to remember is that interviewer i mean the only person to whom you can talk right now is the interviewer right like whatever is going through your mind just talk through them if like uh they are here only to help you out they they are not here to knock you off they don't have any ego issues so they are here to select you that's why you are attending the interview with them so try to whatever is going through your mind just try to walk through them so if you are even if you are stuck somewhere they will definitely give you some hints and then you know you can progress further and then once you once both of the parties are aligned to us as a solution or an algorithm then i would recommend that you start coding yeah i think that's fantastic advice um start with a verbal solution that's the best and you can get cues from the interviewer on whether you're on the right path or just really iron out those kinks before you start getting code down yeah thanks so much russian this was fantastic i am very sorry that i put you on the spot but also you've really dealt with that fantastically so thank you i was expecting from an fba engineer come on and good luck with your upcoming interviews thanks so much for watching don't forget to hit the like and subscribe buttons below to let us know that this video is valuable for you and of course check out hundreds more videos just like this at tryexponent.com thanks for watching and good luck on your upcoming interview [Music]

Channel: Exponent

Views: 2,413,501

Keywords:

Id: thkuu_FWFD8

Length: 40min 33sec (2433 seconds)

Published: Mon Apr 12 2021