Inorder Traversal (Python)

Watch someone solve the inorder traversal problem in an interview with a FAANG engineer and see the feedback their interviewer left them. Explore this problem and others in our library of interview replays.

Interview Summary

Problem type

Inorder Traversal

Interview question

1) Given the root of a binary tree, return the inorder traversal of its nodes' values. 2) You are given a large integer represented as an integer array digits, where each digits[i] is the ith digit of the integer. The digits are ordered from most significant to least significant in left-to-right order. The large integer does not contain any leading 0's. Increment the large integer by one and return the resulting array of digits.

Interview Feedback

Feedback about Mythic Platypus (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?

4/4

Strengths: + TC was able to come up with the solution for both of the problems. + TC was able code the second problem by themselves. + TC has good debugging skills. TC debugged issues in their code. + TC was able to communicate their ideas clearly. + TC was good listener. TC took on hints and improved their code for the first problem. + TC was able to analyse the complexity of second problem correctly. Improvement Areas: - TC struggled with redundant code. They should try to avoid this. - TC wrongly analysed the complexity of their first problem's approach. - TC struggled with converting recursion into code. Suggestion: Practice bit more on recursion and binary tree and schedule one another practice interview.

Feedback about Red Maelstrom (the interviewer)

Would you want to work with this person?

How excited would you be to work with them?

3/4

How good were the questions?

4/4

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

4/4

This was the first mock interview where I felt totally comfortable and felt like I could ask questions. This is also the first mock interview I've done where I completed two coding questions. In other cases, it took me 45 minutes to get through one. You were very helpful during this interview. Keep up the good work!

Interview Transcript

Red Maelstrom: Hello.

Mythic Platypus: Hi.

Red Maelstrom: Hi. Can you hear me?

Mythic Platypus: Yes.

Red Maelstrom: Cool. Awesome. So we'll spend like 45 minutes on coding problem, last 10-15 minutes for feedback. So before we start, can you tell me like, do you have hard stop after 1 hour or it's okay to go a little over?

Mythic Platypus: I have a hard stop after 1 hour.

Red Maelstrom: You have okay, I will try to keep it as close to 1 hour as possible. Okay, cool. So this is the first question. You have a root of a binary tree and you have to return the in order traversal of its node.

Mythic Platypus: Okay. So in order traversal, that would be the order where the left nodes are returned. Then let's see. So if I have that's going to be hard to draw a tree, but I'm thinking of in order I'm thinking of going down the left subtree and then returning that left leaf, then returning like, its parent and then returning the right node. Is that correct?

Red Maelstrom: What would be in order to this? Correct? Yeah.

Mythic Platypus: Okay. And then we have a binary tree, and that means that each node has at most two children. Okay. Yeah. Let's see. Do I need to choose my language?

Red Maelstrom: Yeah.

Mythic Platypus: So given the root of a binary tree, return the in order traversal of its node values. So I need to write a function, and I'm given the root of the tree and like, in this example, given the roof, the tree before, and I need to basically return an order traversal. So I'm thinking that I want to take maybe take a recursive reproach. So if my tree if I'm giving none as a route, then I just basically return none. Yet if the root of this tree is valid, but it doesn't have any children, I'll just return the root value. Those are my two base cases or cases that I think of immediately. And I know that I want to return the left subtree or the left leaf node, node, parent node, and then the right node. So let me think.

Red Maelstrom: How would you define a tree node?

Mythic Platypus: How would I define a what node?

Red Maelstrom: Binary tree node.

Mythic Platypus: I don't think I understand the question.

Red Maelstrom: Like, how would you represent a tree node? Like, will it be a class? Like, how does the tree node class looks like?

Mythic Platypus: Oh, that's not given. I assume it'd be some sort like, a node with value and I'm sorry, the value left and right.

Red Maelstrom: Okay.

Mythic Platypus: Yes, left and right pointers.

Red Maelstrom: Okay.

Mythic Platypus: I know that I want to get down here. So I started the root node, and then I checked to see if the root node has like, a left subtree or like, a left node. And if it does, then I would like, repeat the check if it has a left or right subtree. But if it doesn't, then I can return this value and then it would backtrack and it should visit this node again and return it. And then it should visit this node and return it. So how do I code that given the root? I'm given the root of a tree and I want to return the in order traversal of its nodes values. I have these two checks in the beginning. If root is none, then return none. And if that's not the case, if root left equals none and root right equals none, and I just return root value. Those are like my base cases. Now I need to think about how to think about the case where I have a left and right child. Let's see, think about it up here. If root has left subtree left child, then I need to basically call this function again like a recursive call. It would be like in order route. And now I'm hitting a bit of a difficulty because I know that it can return the value of the get to a leaf node. I know it will return the value, but I'm struggling to figure out how to get the parent node, I guess, printed out before that. Right? Sub tree node.

Red Maelstrom: You don't need to print out. You need to return a list. So the output is expected as a list of this.

Mythic Platypus: I don't need to return them.

Red Maelstrom: I just need to you don't need to print. You need to return a list. You need to create a list and return it.

Mythic Platypus: Okay, well now that changes things. I need a minute to think.

Red Maelstrom: Sure.

Mythic Platypus: I can't do recursive because I need to add on to the list instead of adding or creating a new list each time. So I need to figure out the structure of how the structure of this code.

Red Maelstrom: Can't you update a list that you got from left subtree? The list that you got from right subtree?

Mythic Platypus: I'm sorry, could you repeat that?

Red Maelstrom: Can you just obtain the list? Let's say, for example, if you get sorry, list from left, I think there is an eco. I don't know why. So if there is a list from left subtree and if there is a list from right subtree, you can append them?

Mythic Platypus: Yes, I can do that.

Red Maelstrom: Base case is already taken care of. You just need to worry about recursive it. Cursing. It like, let's say like so you call a left side and you get a left list, right?

Mythic Platypus: All right.

Red Maelstrom: Right. How will you append them?

Mythic Platypus: I would just do left list plus right list.

Red Maelstrom: You also need to append the value of this current node in between, right?

Mythic Platypus: Yes. Okay. If I look at the code that I have now, I have a result list which is empty, and I'm starting at the root node. If the root node is none, then I return none. Or I guess if it's not, I want to return an empty list instead. If it's just the root, then I just need to return the root value. I don't think that's completely right. Because if I'm calling on this like recursively. It's not adding to the list. It's returning a single A list with a single item in it. I need to edit result and then return result. There you go. Let's see.

Red Maelstrom: So if you are creating result, then do you want to return the result?

Mythic Platypus: I don't want to return the result because that would cause the function to basically end. Okay, so now have this case out here. And then once we get to this line, it's going to call order in order and it's going to return or it's going to have this as the parameter. And this can either be because the next node really doesn't exist on this side, or it can actually be another node valid node.

Red Maelstrom: You already check. Even if you go to the none, your base case will be taking care of it, right?

Mythic Platypus: Right. Correct. Here I'm thinking at the end of this, I do, I know I need to add the left list plus the current node plus the right list. So I need to do this. This I don't think that will work. Okay. Because I wanted just to add sorry. I wanted to make it a list value. I don't think that works in Python. So.

Red Maelstrom: Do you really require the case? This condition at line number 29?

Mythic Platypus: What about the condition at 29?

Red Maelstrom: Do you need it? Because like, even if you go to the non node you are taking care of. Right.

Mythic Platypus: I'm a little confused because if I pass a route like a non node in, then we return empty.

Red Maelstrom: Right?

Mythic Platypus: But 929 is the case where the route is valid.

Red Maelstrom: Right. Let's say you pass five to line number 29, right. And if you don't have this condition, you will end up calling none and none for left and right. And you will get two empty list and just append five in it. Right. So this.

Mythic Platypus: Basically does the same. It does the same thing. I see. Just a step to do the same thing. Okay. So if that is the case, then this is not necessary because it just repeats the same, right?

Red Maelstrom: Yeah. Cool. Awesome. I think this should work. Let's move to the second question. What would be the complexity of your code?

Mythic Platypus: The complexity of this here?

Red Maelstrom: Yeah.

Mythic Platypus: So it's traversing the tree and the binary tree and it's going to visit each node once. Would it be for the time complexity of log in? And then the space complexity would be.

Red Maelstrom: Login. Why would be the login for the.

Mythic Platypus: Time.

Red Maelstrom: What is N? There.

Mythic Platypus: Is the number of nodes.

Red Maelstrom: How it would be logged in.

Mythic Platypus: Because it's a binary tree. So it's basically looking at half of the nodes each time, I believe.

Red Maelstrom: But you would be visiting each node at least once, right?

Mythic Platypus: Right. Yes, that's true. I will be honest and say I'm not well versed in trees. This is probably one of the few tree questions I've actually practiced on. I know that binary trees that when you traverse them I guess that the time complexity is O of log in.

Red Maelstrom: Yeah, actually I put the order of n because you would be visiting every node. Right.

Mythic Platypus: Okay. I see.

Red Maelstrom: Understood. Cool. Let's move to the second question. Like I have posted the second question at the top.

Mythic Platypus: You are given a large integer represented as an integer array of digits where each digit is the 8th digit of the integer. The digits are ordered from most significant to least significant and left to right order. The large integer does not contain any leading zeros increment the large number the large integer by one and resulting return the resulting array of digits. Okay, so look at the first example. I have one, two, three and I just want to add one to it. The array represents the integer 123. Okay. Okay, so I'm just basically given an integer and I need to add one to it and return the resulting array of digits. Okay, so let's see. Okay. And I'm always going to increment the digit by one. I don't have to carry a digit over and there's a case where I do have to carry a digit over. Let's see if I'm looking at the first case one with one, two and three I can go over to the ones place, get the value from there and add one to it and then basically replace the three and have the new digit included in there. But if I look at this third example here, I just can't simply replace the I can't just replace that element because I would need to have two different elements in the output array. So my first thoughts it is that I can make it a bit easier. I can reverse the array and then I know once I reverse the array I'll have the ones place in the very front and so I can add one to the ones place. Then I have like the two cases I have to think about need to carry and don't need to carry. After I consider all of those cases then I can reverse the array and then return it. So if I need to carry, I can have that being I can indicate that with a variable if this variable is true, then I do the addition. I'm sorry. If I need to carry, then I'll indicate that with the variable like a true or false variable. And then if I need to carry, I know that the one's place digit is nine and that nine needs to turn to a zero. So I will replace the nine with a zero and then I would increment the next digits place. In the case of me starting with the ones place, I'd go on to the ten, the tens place and then I would just add one there. But also I still need to check if I need to carry because if I have a number like 1999 more than once and then if I don't need to carry and I just replace or just simply add one to the digit. Okay. Is this approach clear?

Red Maelstrom: Yeah, I understand it how it will work on this case.

Mythic Platypus: So if this is the example I have, the first thing I would do is reverse it to this number. And then second step, you add one to the ones place. And so I need to carry in this case because I'm working with a nine. And so like I said, I would have a carry variable evaluate to true this nine would become zero and then I would iterate to the next spot right here. The carry variable would still be true. So I would change this to a zero as well. And then when I get to this next place after the evaluations are done and my carry variable, what do you call it? When my carry variable evaluates stuff off, all I'll need to do is simply add one to this place, it'd be nine and then I just return this reversed again.

Red Maelstrom: Cool. I think. Yeah. What would be the time complexity of this?

Mythic Platypus: Of this? So reversing the array itself would be a time complexity of N and then this would be a loop that would be O of N as well. And then this version array again is O of N. But when I reverse the array those are like outside of this loop. So the overall time complexity of this looks like it's going to be O of yes. If you don't reverse your array, you can just iterate to the end of the list, add one and then you can continue with the same loop. But you would have to go backwards. Yes, I think it's possible to do it without reversing the array.

Red Maelstrom: Okay.

Mythic Platypus: So which one should I code first without reversing? If I want to just add one to the ones place, I need to get to the very last digit. So I can do that with going to go backwards one. Okay. So starting at the end of the list, I'm just going to copy this down lower so I can see it. Okay. So I want to add one to the ones place. So I need to see whether or not I need to carry. And I do this by if the array at this position is equal to nine. If it is, I'm going to have a variable initialize it to false. If the array of this digit is equal to nine, then I know I need to carry. So my carry needs to be set to true. Let's see if that's true. Let's see. I need to update this digit to zero. Okay. If the array at this digit is equal to nine, I need to carry. After I set carry to true, the array at this particular digit turns into a zero and I need to increment the next digit by one only. If I don't have to carry. Okay, let's this is going to get messy, I guess, before it gets clean.

Red Maelstrom: Do you need this? Like, you already turn back to it, right? If it is not going to get carried, then you will just break the forward loop.

Mythic Platypus: Okay. I'm doing I'm trying to do a lot of work in one loop. Okay, I see. Okay. I'm going backwards. If I need to carry, that means that the digit I'm at is equal to nine. And then I could just change this digit to zero else at this variable equals.

Red Maelstrom: I think yeah.

Mythic Platypus: Okay.

Red Maelstrom: Do you want to test it?

Mythic Platypus: Okay? Yes, I'll do that. I'll just return here at the end. Okay. So I'm working with one, two, and three. I'm going to have for I in range. Okay. So the length of this array is three. It's going to start at two until it gets up to negative one. You just wanted to actually print it out. Okay. That is not what we want. We only want to increment it by one. Okay. So where am I going wrong here? So I want to start at the end of the list, and if I need to carry, then I carry.

Red Maelstrom: Do you need to break the loop and it will start where you increment it?

Mythic Platypus: Yes, I know I need to break the loop. I'm just trying to understand where because, like, in the case that I just only have to carry once, I think this is fine. And I can increment or I can just break. But I'm curious about, like, when I have two nines in my number.

Red Maelstrom: Yes, sir.

Mythic Platypus: I think this could work for here. It works for this case because right now I'm only editing my carry value once, but I might need to fix it.

Red Maelstrom: Do you mean something like this?

Mythic Platypus: Yes.

Red Maelstrom: Do you want to try anything for this properly?

Mythic Platypus: Okay. I'm sorry.

Red Maelstrom: I think it will fail for all nines if everything is nine.

Mythic Platypus: Okay, I see. Okay. I was worried that it wouldn't register all the nines I see now, but.

Red Maelstrom: For all nines, I think it's fulfilled.

Mythic Platypus: Okay, well, that is another case I need to get finished, like whenever I need to add a digit. Okay, interesting. Okay, let's see. I know I need to add a digit whenever my carry variable is still true on the most significant digits.

Red Maelstrom: Right.

Mythic Platypus: So let's see. Right now, I'm just replacing the digits. I need to have some sort of condition or write it some sort of condition that will tell me whether or not I need to add a digit and then I can just insert right. I feel like there's like, subcases with this one too. You have nine, nine, nine. You can also have something like 1000. No, that'd be fine. Okay, I see now. Okay.

Red Maelstrom: You can even count if everything is nine. Right. You can have counter. Like if everything is nine months, depending.

Mythic Platypus: I would do this outside of the loop? No, because if I do it outside of the loop at the very end, then none of the nines would be there. There'd be all zeros.

Red Maelstrom: Yeah. So you already have this condition here. You can just increment the count.

Mythic Platypus: Okay, I guess I'll do it at the beginning. So if of the array count of nine is equal to the length of the array, it should be. I'm thinking I should indicate that with a variable and then like, look at that variable at the very end. So at the beginning of the loop or right before the loop, I would count the number of nines. And if the number of nines is equal to the length of the array, I need to set something to true. So like, I guess add a digit that will be set to true. And then once I get at the end of this for loop, I can say if add digits true, then I can do the array right at the beginning. Position one. Okay, I run this.

Red Maelstrom: Awesome.

Mythic Platypus: It works perfectly. Okay.

Red Maelstrom: Does it work for the previous cases.

Mythic Platypus: The time complexity of this function? Let's see. So I have some if statements, which is constant. I have some initializations constant. I have this loop here. Okay. So the bottleneck of this function is this for loop here. And this for loop is only iterating an array backwards. So all the elements in the array, I would consider that to be N. So I think the time complexity of this would be O of N.

Red Maelstrom: Cool. Yeah, that's correct. Do you want to drive another program or you have hard stop?

Mythic Platypus: I kind of have a hard stop. I don't think I'll be able to answer the next question in the next 15 minutes.

Red Maelstrom: Okay.

Mythic Platypus: I just want to talk about feedback and whatnot what I can do better. I know you have an evaluation, write it down. But is there anything that we can talk about now?

Red Maelstrom: Yeah, I like that. For the first problem, even though you were new to the binary space, you identified that it would be a recursive approach. So you communicated it correctly that it would be a recursive approach to solve the problem. Then you came up with base cases. Like when the tree is none, allude root has no children. Like those cases. Right, right. You came up with the appropriate structure for the node. You converted your base cases into code easily. I think there was redundant case, like only root personal was required. Base case. Right. And that should be sufficed. So the case was not required. Maybe with the practice you will understand this, like why what cases are redundant? So my solution would like to practice a bit more on the recursion and a binary. I have shared a link at the top for the binary tree as a resource.

Mythic Platypus: Okay.

Red Maelstrom: So my session would like to go through the basics of it. I think you mentioned the time complexity would be logging, whereas like the time complexity was N, which was a big difference. But yeah, as you mentioned, you are new to binary trees. It is expected. But yeah, the second question, I really like the way you approach. You clarified that it will always be increment by one or will it differ by one or two or three, things like that. You clearly identified the case where you need to either carry or you don't need to carry. Right. You shared a step by step approach. I really understood what you are trying to think. But I think the carry was not used. This variable carry was never used. So that was again a redundant code. In your code, if you see carry is never used. It's initialized, but it's never used. The expectation would be like even at least if you are using it. But after the code, you are done with the code, you can identify what is your redundant code and remove it. This carry was never used.

Mythic Platypus: All right. This served as the carry variable basically.

Red Maelstrom: Right?

Mythic Platypus: Okay.

Red Maelstrom: Yeah. I think initially you missed breaking from the loop and end up incrementing everything. But you were able to debug it and figure it out what is the issue and debug it. So that's all good. I think you also handled the edge case of all being nine correctly. So yeah, I think in the second problem, you did really well based on this overall interview. It would have been higher call, let's say. For example, this would have been a phone screen. I would have asked, given a recommendation, to move to the next step and call forth on site. But yeah, my session would be like to practice a bit more on binary trees and recursion so that those glitches goes away.

Mythic Platypus: Okay, cool.

Red Maelstrom: Do you have any questions for me?

Mythic Platypus: Let's see, I guess when you were on my side interviewing, what did you do to prepare specifically while you were in college? How did you prepare for interviews while handling school work at the same time?

Red Maelstrom: Yeah, so I kept a target of like having solving at least two, three problems a day. Two was the target for me. I just not go into coding. I just don't try to get the solution coded. So I use the lead code. So basically I used to write down the approach in plain English language initially so that I get a practice of articulating my thoughts and then analyze the complexity of my solution and then start coding the problem. And I will try to come up with my own test cases so that solution gets accepted in a first go. My target was not to solve multiple problems with the good speed. My target was like to get solution accepted in a first quote. So I will try to force myself to think about test cases before submitting the code.

Mythic Platypus: Okay.

Red Maelstrom: So that I get in the habit of identifying the issues in my code.

Mythic Platypus: Okay. And my next question is, since a lot of the interviews are virtual, how.

Red Maelstrom: Do you.

Mythic Platypus: Try to visualize or show your interviewer what you're thinking? Because it's kind of hard to like I was thinking I didn't know how to draw a key or draw a tree in this coding environment. So is there any tips on how you can show your interview what you're thinking, even if it's virtual?

Red Maelstrom: Yeah, so you can use the excalidraw so you can say that maybe I can share my screen. You can use excalidraw to draw things for the discussion point, and then you can stop sharing your screen once you share your thoughts.

Mythic Platypus: Okay, got you. Okay, I'll keep that in mind.

Red Maelstrom: When are your interviews?

Mythic Platypus: I have one coming up in January.

Red Maelstrom: Oh, my you still have time. Okay.

Mythic Platypus: Yeah.

Red Maelstrom: Awesome.

Mythic Platypus: I'm still applying, but yeah, that was.

Red Maelstrom: All the questions I understood. Cool. Awesome. Then I will give you your eight minutes back. All the best for your upcoming interviews. My suggestion would be to practice a bit more on binary trees and recursion, and maybe she is one more interview to make sure that you go through it.

Mythic Platypus: Okay. Yeah, of course. Thank you so much for your time today. This is really helpful.

Red Maelstrom: Thank you. I think you need to write a feedback after this, so please do that.

Mythic Platypus: Okay. All right. Have a good rest of your day.

Red Maelstrom: You too. Bye.