Delete Nodes from a Binary Tree (Java)

Watch someone solve the delete nodes from a binary tree problem in an interview with a Google engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Delete nodes from a binary tree

Interview question

1) Debug this piece of code. 2) We want to delete certain nodes from a binary tree. We have a function `shouldDelete(TreeNode node)` that returns true if we should delete that node, you can assume this function already exists. Write a function `deleteNodes(TreeNode root)` that takes a binary tree which removes the nodes that should be deleted from the tree and returns a forest of trees.

Interview Feedback

Feedback about Kind Ibex (the interviewee)

Advance this person to the next round?

How were their technical skills?

3/4

How was their problem solving ability?

3/4

What about their communication ability?

3/4

You have a good methodical and logical approach to problem solving, I don't have any suggestion here, good job. Communication: Explain your approach to the interviewer before you start writing code, it is a good idea to bring up the time complexity of your solution as well. Don't feel obligated to step through your code out loud. Coding: Keep your indentation consistent. Use a helper function if you need to when writing recursive functions. It is more typical to use an interface type for the return value of a function instead of a concrete type, e.g. List instead of ArrayList.

Feedback about Talking Fox (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

4/4

How good were the questions?

4/4

How helpful was your interviewer in guiding you to the solution(s)?

4/4

You were the first interviewer who focussed more on the thought process than speed. It makes me feel better so thank you on that. You had a good exercise in the beginning to break the ice so that was good too.

Interview Transcript

Talking Fox: Hello.

Kind Ibex: Hi can you hear me alright?

Talking Fox: Hi. Is this a good time for you? It will take about 45 minutes.

Kind Ibex: Oh yeah, I was waiting for you.

Talking Fox: Okay so let's start by doing some introductions and then taking a look at some code.

Kind Ibex: Okay.

Talking Fox: So I can start by telling you a bit about myself. So I was a software engineer at Google for about six years. I worked a lot of the time in Geo, so I worked on like the Maps front end and I worked on the android client for location sharing.

Kind Ibex: Okay.

Talking Fox: So you can stay anonymous if you want or you can tell me a bit about yourself either.

Kind Ibex: So I actually work in Intel. I graduated last year and right now working in the devops team for year. I have my essary interview day after at Google, so I am just trying to see if I can make it this time.

Talking Fox: Sure umm so for the essary interviews, you do like some like coding interviews and then some other like more like essary specific ones right?

Kind Ibex: Yeah but for me I think it's like, I don't have a lot of experience so it's just holding down.

Talking Fox: Oh, interesting.

Kind Ibex: One behavior, that's it. Leadership round.

Talking Fox: Interesting okay. I know for like some essaries is they asked them about like networking and talk about like Linux. Ok so if it's just coding, then I think we're good. Ok um so which programming language did you want to use?

Kind Ibex: Java.

Talking Fox: Okay sounds good. We can just delete that. So we can start off by doing some debugging so I'm going to paste in some code and has some bugs in it, so I want you to take a look at it and try and fix the bugs.

Kind Ibex: Okay. So it's to reverse an individual array to get the link and end first, you travel from 0 to n which is good. Value assign values. i is equal to values n minus i. Okay I think it's going to be n - i - 1.

Talking Fox: Yeah that's right.

Kind Ibex: So I'm looking forward to... I mean to swap right? So I need a temporary variable.

Talking Fox: Yep yeah that's right.

Kind Ibex: So your values i like this i like this one your template. And this would be n/2 I think because I don't need to travel the entire thing again. I need to come to the middle.

Talking Fox: Yup, that's right.

Kind Ibex: But there's just one thing which I am thinking right now is whether there should be n/2 or n/2 - 1. So if it's an even, so for example if this is the case with four numbers, my n/2 would be 2, so 0 1 2 and I need to travel only 0 & 1, so this is good. If I have some suppose another number to 5, then I travel so this is like 5/2 is 2, so is 0 1 2 and here I will be like swapping the same thing, so it's fine. Yeah so I'm good there. Do you want me to run this?

Talking Fox: So I think like the reverse function looks good, so why don't we take a look at the main function.

Kind Ibex: Okay so you call this reverse function, you pass on the values, then you try to print the values of the reversed values. The reverse would every nine, would be reverse of one is 55. But okay and for 53 it will be like the reverse of the reverse of 53. Is that something you're looking for or no.

Talking Fox: Um yes, so like it kind of looks like the output should be, like the first line should be, like 1 ro 55, but what we're going to get is 55 ro 55.

Kind Ibex: No so you have values pass on your, but... Oh so the array values is changing is what you mean. So I think it little again (n - i)/2 - 1. Um yeah so I mean that will work like if we do that we'll get the right output. I guess like the real issue is that we're like modifying this values array. Um and like this like reverse function is sort of confusing because it like takes this array and then like also returns an array, so like if it returned void it is like be more obvious what it was doing.

Talking Fox: Yeah.

Kind Ibex: Okay let's try another question. I'm going to paste it in at the top. If you've seen this one before you can tell me and we can try different one.

Talking Fox: Given a two-digit map of London... yes I have seen this, it's the DFS.

Kind Ibex: Okay all right yeah, let's try another one. We want to delete certain nodes in a binary tree. We have to delete tree node. That returns true if we should delete that node. You can assume that this function already exists. Delete the function that returns true if we should delete that node. Write the function delete nodes tree nodes root that takes a binary tree which removes the nodes that should be deleted from tree and returns a forest of trees. Okay so here, okay I haven't seen this question. Okay so what I will be passed this root, that means a, and then I will have a delete nodes function, which pass... which has my root, which is a right here in this example. And I need to like, whenever I find a node, I just need to return and check if that should be deleted. If that's true and I should delete that.

Talking Fox: Yeah.

Kind Ibex: Okay and one thing I am not sure about is what do you mean by return the forest of trees like...

Talking Fox: Umm yes so say like here if we were deleting A, so then we would get back like two trees B and C.

Kind Ibex: Okay.

Talking Fox: So forest of trees is just like a collection of trees.

Kind Ibex: Okay. Ok so I have my... So maybe it will be like a list of trees, it might be a list of trees so... Return tree. And so here I check if... So if I have a removed, I'm... Ok I'm thinking if I should remove A at the first instance or I should just travel down, go to the leaves, and then come up like basically travel up and then keep checking if it should be deleted, then I should simply delete it. Because if I delete A, then I have two nodes to take care of and then when I increase the level of depth, I might just lose track of all these nodes. So it's better to go down and delete leafwise.

Talking Fox: Yep. I think that sounds good.

Kind Ibex: So I just travel... so I think that would be the order that will be post order traversal, I mean linking like the two nodes first and the two children first and then come to the parent, so it will be post order traversal. So I start with the... So after doing this I'll come to the node, so now I check if my root should be deleted so if delete root. In this case I would delete it and I have my A B C. So A is my root, B and C are the children. B is the root now.So I'll check if B should be deleted. If B should be deleted, then I will basically delete the connection of B with...

Talking Fox: Yeah, sounds good.

Kind Ibex: So that would be parent of root.parent.

Talking Fox: So we don't have a link to their parent in the tree nodes, we just have like left and right children.

Kind Ibex: I think I need to delete stuff from the root level. I will check if so probably like when I'm checking root.left is not equal to null, I should check here if there should be another check here if root.left if should delete root.left, then assign... Then root.left = null. I have to travel to the end and then do that so, I'll go to this level. So I know my... I am on the root of the level A. I know if I will actually... I'm good here. So this is fine. Here I'll check if I should delete my root.left, then I will make roor.left is equal to right. So if I have this tree, my root is A first. My root.left is not equal so I called read nodes on root.left. So I called all this function on B. Now my root.left is not equal to null, so I call it on D. Now my root is D. I root.left is equal to null, so if it doesn't come here, then it comes to if should delete root. So the tree thing will always be from the parent. So I I'll check if should it should be root.left. That means null. That means we would actually pass now so it has nothing to do, so fine I come to, so I backtrack I'm checking on E. Again E would be the same thing, taking for example E should be deleted okay. So I... E is root now, it doesn't have right and left a child, you cannot do anything, then I should then I should check here, this is not required, so I come back now my root is B. Now suppose my E has to be deleted and D does not have to be deleted. So I check if my B root.left is not equal to null. Okay this part is done, till here it's done. Now I am on line number 31 for my root B, so should do root.left, which is B. I should not delete that so I'm not doing anything. Now if should be root.right as is E, I should delete so I will make root.right is equal to null. So here my E is deleted. This is fine. This works. Now what I need to check is if I have to delete B and D still exists. I need to add it in the array list here. So I need to also keep a check that if there are left and right children, then that needs to be added before deleting the... So basically here you should delete root.left. For example if my B should be deleted, my root is A, so if A.left, which is B, should be deleted, then I have to take care of B and E. So I need to add... So what I'll have to add here is result.add. Basically you are adding both the kid's status if B is leader then... I need to check whether B and E are null, so I will also check here. Why is this giving an error?

Talking Fox: Oh maybe try making it static.

Kind Ibex: Yeah and the same thing I need to do here also fixing everything but yeah. If root.right.left is not equal to null, then I will add another rule. root.right.left and if root.right... and then I find this here and in the end I just set default. So as I walk through this... So for example you're given B E, so you have A B C D E F G, your tree here.

Talking Fox: Yep.

Kind Ibex: I have to... Let's mark C as needs to be deleted. Your E should be deleted. I think that covers most of it, like I need to have one leaf with deleted and one middle node somewhere in between should be deleted. Yeah is that fine?

Talking Fox: What about if we had a like this example where we were deleting C and G?

Kind Ibex: Okay let's do that then, C and G. So I passed my A here. I check if my A.left is not equal to null, which is true. So I go to B and then again it traverses the entire side of B at the the left node. Since I have nothing to delete here, so I will just pass that for now. And then I come to my root.right, which is C is not equal to null which is fine. So now I pass delete node root.right for C, so now my root is C. Now I'll check if root.left, which is F is not equal to null, which is true, I'll delete nodes root.left. So I'll pass the F in, F here. And then I check if my root.left is not equal to L, which is F.left and F.right are kids, are children are null. So I pass 27 to 30. Then I come to 30 line number 32, I check if F should be deleted. It should not be deleted. Okay I check if F left and right should be deleted, so I think there's something weird here. So if I am checking if the root at the leaf node should be deleted, but this is not null. I need to keep this inside the bracket here. So basically... So let's do it again, I changed stuff here. I passed my A and my root. As my root I check if my A.left which is B is not equal to null. It is right. So I go inside this. Since the right nodes, root.left, that means it goes on B. Since I'm not doing this, let me come to this part, line number 39. Now my root.right is not equal to C. That's true, so I go to delete nodes root.right, which is C. Now my root is C. Again I check if my root.left is not equal to null, so root left is F,so it's not equal to null, so delete node again call it on F. Now my root is F. I have to check if root.left is not equal to null, but it is equal to null, so it won't enter this. Again, root.right is also equal to null, so it won't enter this. I go back. Now check if my if I should delete my root.left, so now my root is C, so root.left is F. Now F should not be deleted, so I don't go here. I go to root.right, which is G. I go to... I call delete nodes on G then again it comes back here because there is nothing G's kid which needs to deleted. Now I check if should delete on root.right, which is G and this returns true, so I check if root.right.left, that means G's left child is not equal to null. Then I add result if G's left child is not equal to null. There's no left child and there is no right child, so I don't do anything. Now root.right, let me see, is equal to null. That's fine. I go back again now I am on C. Now my root is A and my right, my root.right which is C is not equal to null. I have delete nodes root.right is returning true for C, so I should... should delete should return true for C, so I check if my root.right, which is C.left, that means F, is not equal to null then I add root.right. That means I add F to my result, then again I check if my root.right.right, which is G. Okay but it's already deleted, so I don't have anything on my right. Then I just make root.right, that means A.right as null. Yeah and then, okay so my... Yeah that's fine now here I check if root should be deleted. So if root should not be deleted, then I add my root here. So in the end I just add A here. And A would have connections to... So now my result array has F as one tree node and then it has A as another tree node.

Talking Fox: Um the thing is if we're doing this unlike every iteration will end up with like extra nodes in our result. So like we would get A but in this case we would also get like B D E.

Kind Ibex: Okay. It's okay if I can keep like... So I'll always have A in my result, but the moment I... Otherwise if I have something deleted, then I have such stored. So basically okay, okay I get it. If A is deleted, then I need to store B and C, which would done. But if C is deleted, then I am storing F and G, which is fine, but I have to also keep track of A. So can I just add like result initially here only in the beginning? So here when I am passing, so what I am calling my function of delete nodes, I can just add it to my result and then pass it.

Talking Fox: Um yeah I mean I think that would work because like the root is sort of a special case.

Kind Ibex: Yeah. So I'm adding when it finally has been called by delete nodes. Okay let me call it from here. So I'll just add result. Yes the static variable will be accessible, so it's fine.

Talking Fox: So what about if we were deleting a... E yep.

Kind Ibex: Um I have A added to the result. I delete nodes so I should... When it comes here, when root comes here, I'll just check if I should delete root because I should not delete root. Then results adds this. We're going to do some like more conditions which will actually ensure that even if my if my root is... Okay okay, so if my root.left, okay if it's A, then I come here and I check... Ok this line things, we removed it's not required here. I already added A, so if my left is not equal to null, fine I go and traverse this, do the entire thing for B subtree, and then if root.right does not equal null, I do it for entire C subtree. I have to keep a check of if my roots were deleted so... I'll simply add... but I'm doing that already... Okay let me know if my ... then I should save the result. Try now to see if is this gonna work. So if I am at A, I check if my root is not equal to null. If A should be deleted, then I will see if my left and right child are not null, I'll add it to the product result. I'm just saying like what happens when it comes when my root is C and I'll see my my root is C. And then I'll see if my root.left is not equal to null. F is not equal to null, so I add it here. My root.right is not equal to null, so G I add it here. But again later on when I check this if it should be deleted, then... Okay so here I am... It's like a top down and bottom of both for example here. I need to have a middle place where I am actually deleting, so if I'm adding it here like for C, I will add F and G, but when I go to G, G should be deleted. So I need to remove G from my result.

Talking Fox: I think like what you are doing with the post order before was good, so if you like look at the nodes and delete them from their parent before you add them to the result, then like any nodes that were being deleted have already been like removed, so I feel like this is fine, we just have to do it in the like post order, so like after we do the traversal.

Kind Ibex: So basically... Okay in this case also if C, if it comes to C and C should be deleted, now my root.left is not equal to null which is F, so it will be added, but my G is already deleted, so it's fine. But I think here my G will be in like added to the result twice, so this would...

Talking Fox: Yeah like... yeah like we don't need like here like this part where we're adding the like second level children.

Kind Ibex: But if we remove it from your, I was worried if root.right is equal to null, I need to store that the kids of root.right, before I make it null.

Talking Fox: So it's kind of like say today we're like deleting C um, so maybe that's not a good example... Okay let's try for deleting like C and G, so say like C is like the current node, then we do like this part where we set like G to null then we come down here and C is also being deleted, so we want to add F to the result, but like we don't wanna add G because G is being deleted. But like if we've already set G to null, then we won't add it to the result.

Kind Ibex: Yeah I mean what if it's like A suppose, so I have as my right child, so if I assign my C as null, like A.right is equal to null, I need to keep track of F, because F is still hanging in without getting recorded.

Talking Fox: If we get it like from the bottom up so like we will look at like C before we look at A.

Kind Ibex: So now if I go to C, root.left is not equal to null, I add F here and I don't have to add G because it's deleted. Now I go back my root is A, so A.left is not equal to B, so this first assign coming to A.right, which is C is not equal to null. I pass it to root.right, which is C. I'm already travels it for C, where I've stored if my C should be deleted. I have to assign root.right as null. Okay no sorry this was so my root is C. Now C.left is F and it should not be deleted so I don't have anything here. Now right is deleted, so we go right that means C.right is equal to null. Now I check if should delete C, which is true. So I mark the left and right, check if my left and right is null. So F is not null, so I add` F and F here okay. And when the root becomes A, then A.right would add on it here as null and store B's entire right path. Yeah okay I get this this should work.

Talking Fox: Okay I think that looks good and yeah we're pretty much like out of time as well. So I think like the code, it looks good. I think like the only case we didn't really handle properly is if like the root like A is being deleted, so we should just like check like down here on line 60 before we add it, but the rest of it, it looks fine.

Kind Ibex: Okay.

Talking Fox: I think like when you go to do the interview at Google, I think you're going to be using like a Chromebook instead of like a whiteboard. Um I think like about your code the only thing I'd say is try and like keep that indentation consistent so it's like easier to read.

Kind Ibex: Oh yeah right, when I'm deleting this.

Talking Fox: Yeah apart from that it looks fine, um yeah like I think you did well on this question. Like for like a new grad, this is like sort of like a difficult question, so I think you did really well in it. Um you were definitely like very like methodical and like you know sort of like logical and like your approach to it.

Kind Ibex: Yeah I actually have this speed problem, I don't know like um, I don't know if I'm fast enough for the interview process. Like the other interviews which are I think my speed um it is worrying me for the after.

Talking Fox: I think like definitely like it can be difficult to like finish like the questions like in like the 45 minutes or whatever. Um so I think like I'd say like if you're like checking the code like when you go back and like go through it like line by line, I'd say like unless you're like specifically like looking for a bug or something you probably don't need to like discuss like the whole like line by line execution you know. I think like that would definitely like speed it up, but like on the other hand that's like good for like catching bugs, so I'd say like you probably don't need to do it unless like the interviewer tells you that like there's a bug in your program and like you can't see it just by like looking at the code. Um did you have any other questions any other questions?

Kind Ibex: Any other suggestions you would have or feedback about my code or anything for the last?

Talking Fox: I think like I think your code looks good, I'd say like before you start writing the code like maybe like describe what you're going to do because even if you like come up with a solution maybe it's not really like the most optimal one, so like I'd say like talk it through with the interviewer before you start writing code because maybe there's like a more optimal one that they're looking for. I mean for this for this question like either you use DFS or BFS but like both of them are going to have like the same runtime so that's like not really an issue here, but like definitely with other questions it might be an issue. I don't think I had any other feedback. I say like uh for this code like the way we are doing some work like down here in Maine, like it's more normal to have this function and then have like delete nodes like helper and then like in here we would do like the recursive call and... Actually let me just change it, so did you something put the recursion like in the helper function. And then do this up here. That would be like more normal, I mean it's not really like a big deal though.

Kind Ibex: I get it yeah, makes sense yeah.

Talking Fox: Um yeah I don't have any other comments.

Kind Ibex: Does Google ask a lot of DP questions? Because I think I wrote a function a week back a week or more back and then now I look back to the question I'm like okay I don't know if I can do it.

Talking Fox: I think it like it's definitely possible, you mean like dynamic programming, like it's definitely possible they could ask a dynamic programming question. I mean I never really like to ask them because to be honest it's like not something that I've like ever used, so I feel like it's not really like you fair to ask it, but people like definitely do. I think like sorta like the key thing is like for starters, if you can recognize that it's a dynamic programming question, then if you can like you know you like write out that table and you sure you've seen it, you know you write out the base cases, and then you like work out like how to fill in the rest of the entries using the like previous entries in the table, that make sense?

Kind Ibex: Yeah.

Talking Fox: So I think like that like working at what are the base cases and then what is the formula to like fill in the other cells, so if you can get those like two things, then you've like basically solved the question you know? So I think if you just try and like think about it like that, that might help. Um but I think for like if you said you have like one year experience right?

Kind Ibex: Yeah.

Talking Fox: I think is like pretty unlikely they'll ask something like that and I mean you're going to do like five interviews right?

Kind Ibex: Oh yeah.

Talking Fox: Like even if you don't do so good in like one of them, if you get like good scores in the rest, that's still fine you know.

Kind Ibex: So actually it's a I mean it's an L4 position I think, I have like one years from last and before that I was in school, before that I work for a couple of years, so it's an L4 position.

Talking Fox: Okay, yeah if it's L4, for then yes they may ask dynamic programming.

Kind Ibex: Okay I mean... But I was like okay I'm getting lost.

Talking Fox: Yeah I mean it's not easy and yeah I like I mean I really don't know why it's like become like a popular topic for interviews because like it never really comes up you know, but I guess some people like to ask it. Okay um so yeah I'll write up your feedback and get it back to you. Um yeah I didn't have anything else from my side.

Kind Ibex: Yeah I think I'm done with my questions. Thank you so much for connecting, taking out time.

Talking Fox: Yeah, no problem. Yeah hopefully your interview goes well.

Kind Ibex: Yeah thank you.

Talking Fox: Okay good luck. Bye.

Kind Ibex: Bye.